在 R 中使用 Ackermann 函数避免堆栈溢出

Question

我最近看到一个关于 Ackermann 函数的有趣 Computerphile Video 并尝试在 R 中重新创建它，这是我想出的：

Ackermann <- function(m,n){

  if (m == 0){

    return(n+1)

  } else if (m > 0 & n == 0){

    return(Ackermann(m-1,1))

  } else if (m > 0 & n > 0){

    return(Ackermann(m-1,Ackermann(m,n-1)))

  }

}

在视频中，他们实现了自己的代码版本（我认为是用 C 语言编写的）并解释说，对于特定值对（例如 4,1）需要进行大量递归计算，他们花了 3 分钟计算该值。如果我尝试用我的算法在 R 中重新创建它，我会得到堆栈溢出：

Error: C stack usage  7971652 is too close to the limit

有没有办法在 R 中得到 Ackermann(4,1) 的结果？

Answer 1

我认为这是可能的，但可能相当复杂。如果你这样写（见下文）它不会出错，但会花费一些时间：

sub_Ackermann1 <- function(df){
  i <- nrow(df)
  m <- df$m[i]
  n <- df$n[i]
  if (m == 0){
    r <- n+1
    df$r[i] <- r
    df_i <- df} 
  else if (m > 0 & n == 0){
    r <- NA
    m <- m-1
    n <- 1
    df_i <- df
    newrow <- data.frame(m=m,n=n,r=r)
    df_i <- rbind(df_i,newrow)} 
  else if (m > 0 & n > 0){
    r1 <- NA
    m1 <- m-1
    n1 <- NA
    df_i <- df
    newrow1 <- data.frame(m=m1,n=n1,r=r1)
    df_i <- rbind(df_i,newrow1)

    r2 <- NA
    m2 <- m
    n2 <- n-1
    newrow2 <- data.frame(m=m2,n=n2,r=r2)
    df_i <- rbind(df_i,newrow2)}

  return(df_i)
}

sub_Ackermann2 <- function(df){
  r <- df$r[nrow(df)]
  if (is.na(df$n[nrow(df)-1])){ 
    df$n[nrow(df)-1] <- r }
  else if (is.na(df$r[nrow(df)-1])){ df$r[nrow(df)-1] <- r}
  df_i <- df[-nrow(df),] 
  return(df_i)
}
Ackermann <- function(m,n){
  df <- data.frame(m=m,n=n,r=NA)
  if (m == 0){df$r <- n+1} 
  while (is.na(df$r[1])){
    if (is.na(df$r[nrow(df)])){ df <- sub_Ackermann1(df)}
    else if (is.na(df$r[1])){ df <- sub_Ackermann2(df)}
  }
  return(df$r[1])

}

它至少适用于较小的值，并且不会在较大的值上崩溃。也许有人可以证明这行不通，或者 反之亦然，知道如何优化它...

在 R 中使用 Ackermann 函数避免堆栈溢出

Avoiding Stack overflow with Ackermann function in R

stack-overflow

recursion

r

ackermann