为什么我的记忆装饰器不适用于 Ackermann 函数？

Question

我写了一个可以记忆功能的装饰器，这是它的样子：

def memoizator(func):
    cache = {}

    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    
    return wrapper

我在斐波那契函数上测试过：

@memoizator
def fibo(n):
    if n < 2:
        return n
    return fibo(n-1) + fibo(n-2)

而且效果很好。但是，当我尝试对 Ackermann 函数执行相同操作时：

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

我只能计算

ackermann(3 ,4)

，任何高于此的计算都会导致大量回溯和递归错误。错误消息是您在下面看到的内容，但复制粘贴了 100 次。

  File "c:\path\memoize.py", line 54, in ackermann
    return ackermann(m - 1, ackermann(m, n - 1))
                            ^^^^^^^^^^^^^^^^^^^
  File "c:\path\memoize.py", line 8, in wrapper
    cache[args] = func(*args)
                  ^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded

我可以看出这是一个递归问题，我的 memoizator 无法处理这个野兽。但为什么？有没有一种方法可以编写一个更通用的装饰器来处理这个问题，或者我是否必须为更复杂的递归函数编写专门的装饰器？回溯/错误消息是怎么回事，为什么我得到 100 份相同的东西？

Answer 1

阿克曼函数是一个递归函数，增长非常快。当调用

ackermann(4,2)

时，函数最终递归调用自身

65536

次。错误是因为函数 ackermann 递归调用自身的次数太多了。

Python 的最大递归深度为 1000，因此当您将 m 或 n 的值设置为大于 3 时，函数将达到最大递归深度并导致错误。

控制台重复显示错误信息是由于装饰器实现了memoization。由于该函数递归调用自身，装饰器无法有效地检查该函数之前是否已被调用并检索缓存的结果。结果，装饰器不断调用原始函数，导致重复错误和错误消息溢出。