编写Memoization装饰器遇RecursionError，递归斐波那契问题求助

问题重现 #

为理解Memoization原理，自行实现了缓存装饰器，应用到递归斐波那契函数时，直接调用fib(10000)会触发RecursionError: maximum recursion depth exceeded while calling a Python object，但逐步递增调用（如先fib(400)、fib(800)直到fib(10000)）却能正常运行。

附实现代码：

缓存装饰器 #

def memo(fun):
    cache = {}
    def temp(*args):
        KEY = (fun, args)
        STORED_VALUE = cache.get(KEY)
        if STORED_VALUE is None:
            VALUE_TO_STORE = fun(*args)
            cache[KEY] = VALUE_TO_STORE
            return VALUE_TO_STORE
        return STORED_VALUE
    return temp

递归斐波那契函数 #

@memo
def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

原因分析 #

这个错误和装饰器实现无关，核心问题是Python的默认递归深度限制（默认约1000层）：

• 直接调用fib(10000)时，即使有Memoization，第一次计算必须从fib(10000)开始，依次递归调用fib(9999)→fib(9998)→…→fib(1)，这个调用链的长度是10000，远超过Python默认的递归深度上限，因此触发栈溢出错误。
• 逐步递增调用时，比如先调用fib(400)，缓存中已经存储了fib(0)到fib(400)的所有结果；再调用fib(800)时，递归链只会从fib(800)延伸到fib(401)，之后的fib(400)及以下直接取缓存，此时递归链长度仅为399，未超过限制；同理到fib(10000)时，递归链长度仅为当前n与已缓存最大n的差值，自然不会触发错误。

解决方案 #

1. 临时调整递归深度限制（不推荐生产环境） #

可以通过sys.setrecursionlimit()手动提高递归深度上限，直接调用大n的斐波那契函数：

import sys
sys.setrecursionlimit(100000)  # 把递归深度上限调到10万

@memo
def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

print(fib(10000))  # 此时可正常运行

⚠️ 注意：这种方式有风险，因为操作系统对进程的栈空间有上限，过度提高递归深度可能导致程序直接崩溃。

2. 改用尾递归实现（模拟优化） #

Python本身不支持尾递归优化，但可以把斐波那契改成尾递归形式，结合Memoization减少实际递归链长度：

def memo(fun):
    cache = {}
    def temp(*args):
        KEY = (fun, args)
        STORED_VALUE = cache.get(KEY)
        if STORED_VALUE is None:
            VALUE_TO_STORE = fun(*args)
            cache[KEY] = VALUE_TO_STORE
            return VALUE_TO_STORE
        return STORED_VALUE
    return temp

@memo
def fib_tail(n, a=0, b=1):
    if n == 0:
        return a
    return fib_tail(n-1, b, a+b)

print(fib_tail(10000))  # 结合缓存可正常运行

尾递归的特点是递归调用是函数的最后一个操作，虽然Python不会自动优化，但结合Memoization后，重复的参数组合会直接取缓存，实际递归深度会被大幅压缩。

总结 #

这个场景是Memoization的合适示例——它确实把斐波那契的时间复杂度从O(2ⁿ)降到了O(n)，问题仅源于Python的递归栈限制。如果坚持用递归实现，上述两种方法都可以解决直接调用大n的问题，其中尾递归的方式更安全可靠。

内容的提问来源于stack exchange，提问作者Álvaro Antônio