是否可以在不超过最大递归深度的情况下计算递归 ackermann(m,n) 函数，其中参数 m>=4 和 n>=1 in python？

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

是的。可以使用 sys.setrecursionlimit 和更多的数学来改进算法。 Python 代码见 Rosetta Code task。

注意！

我刚刚重新运行 ack2:

%timeit a2 = ack2(4,2)
1000 loops, best of 3: 214 µs per loop

len(str(a2))
Out[9]: 19729

答案中有将近二十千位数。

Answer 2

对于这个级别的响应，使用动态规划：memoize函数。这意味着您保留了 table 之前的结果。如果您发现已经计算出的结果，那么您可以从 table 中 return 它。只有当它是一个新调用时，您才进行计算——在这种情况下，大部分或所有递归调用将在 table 中。例如：

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)

是否可以在不超过最大递归深度的情况下计算递归 ackermann(m,n) 函数，其中参数 m>=4 和 n>=1 in python？

It is possible to compute recursive ackermann(m,n) function with args m>=4 and n>=1 in python without exceeding max recursion depth?

python

algorithm

recursion

ackermann