使用Ruby中的Ackermann函数"堆栈级太深"

Question

我正在使用Ruby v1.9.1为大学的班级编写一个带Ackermann函数的程序.代码如下:

def ackermann(n,m)
  if n == 0 && m > 0
    return m+1
  elsif n > 0 && m == 0
    return ackermann(n-1,1)
  elsif n > 0 && m > 00
    return ackermann(n-1,ackermann(n,m-1))
  else
    puts "Wrong input, m and n must be higher than 0"
  end
end

puts ackermann(5,5)

这是一个高度递归的功能.所以我得到错误"堆栈级别太深(SystemStackError)".有没有办法或解决方法来修复此错误？

Answer 1

记住递归调用。制作 { [int, hyperlong] => hyperlong } 的映射，以使用动态编程方法来耗尽堆栈空间。

这是一个 C++ 示例：http://pastebin.com/tVQ7yB31

已知错误：ack(3, 10) 占用超过 3 GB 堆内存。