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

Question

可以在不超过最大递归深度的情况下ackermann(m,n)使用参数m>=4和在 python中计算总可计算递归函数吗？n>=1

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

对于这个级别的响应，使用动态编程：记忆函数。这意味着您保留了以前结果的表格。如果您发现已经计算过的结果，则从表中返回它。只有当它是一个新调用时，您才会进行计算——在这种情况下，大部分或所有递归调用都将在表中。例如：

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

答案是将近两万位数。