是否可以在python中计算参数为m>=4和n>=1的递归ackermann(m，n)函数，而不会超过最大递归深度？

Question

可以在Python中使用参数m>=4和n>=1计算总计可计算递归函数ackermann(m,n)，而不会超过最大递归深度？

def ackermann(m,n):
    if m == 0:
        return n+1
    if n == 0:
        return ackermann(m-1,1)
    else:
        return ackermann(m-1,ackermann(m,n-1))
ackermann(4,1)

Answer 1

对于此响应级别，使用动态编程： ememoize 函数。这意味着您可以保留以前的结果表。如果您找到已经计算的结果，则将其从表中返回。只有当是一个新调用时，您是否进行计算 - 在这种情况下，大多数或全部递归调用都会在表中。例如：

import sys
sys.setrecursionlimit(30000)
memo = {}
def ack(m, n):
    if not (m, n) in memo:
        result = (n + 1) if m == 0 else (
            ack(m-1, 1) if n == 0 else ack(m-1, ack(m, n-1)))
        memo[(m, n)] = result
    return memo[(m, n)]
print ack(3, 4)
print ack(4, 1)
print ack(4, 2)

由于记忆使用，您仍然会遇到任何大型 ACK（4，2）>的问题。

125
65533
Segmentation fault (core dumped)

Answer 2

是。可以使用sys.setrecursionlimit和更多数学来改进算法。请参阅Python代码的Rosetta代码任务。

注意！

我只是重新启动ack2：

%timeit a2 = ack2(4,2)
1000 loops, best of 3: 214 µs per loop
len(str(a2))
Out[9]: 19729

答案中的数字近二十千个数字。