为什么自定义memo字典的记忆化递归表现优于Python的lru_cache？

核心原因是lru_cache装饰器会给每次函数调用带来额外的Python栈帧开销，而自定义记忆化逻辑无这部分额外消耗：

• 你的自定义记忆化逻辑直接写在fib函数内部，每一次递归调用只会新增1层Python栈帧。Python默认递归深度限制约为1000，因此可以支持到n≈900的计算才触发栈溢出。
• lru_cache作为装饰器本质是对原函数做了一层逻辑包裹（负责缓存检查、结果存储），调用被装饰的fib函数时，会先执行装饰器的包装逻辑，缓存未命中时再调用你编写的原fib函数，两次调用都会计入Python递归深度统计，因此每一次递归调用会新增2层栈帧，在n≈500时就会触达1000的递归深度上限触发报错。

你观察到的lru_cache生效是正常的：缓存逻辑本身没有问题，第一次调用完成后所有计算过的n的结果都会被缓存，后续调用相同参数可以直接返回，不需要再次递归。

方案1：修改递归深度限制（临时可用，不推荐大n场景） #

在代码开头调整Python递归深度上限，即可让lru_cache版本达到和自定义版本相同的支持上限：

import sys
sys.setrecursionlimit(2000)

该方案仅适合小范围调整，递归深度过高可能导致解释器栈溢出崩溃。

方案2：改用迭代实现（推荐） #

从根本上避免递归深度问题，无论n多大都可以正常计算，同时保留lru_cache的缓存能力：

from functools import lru_cache

@lru_cache(maxsize=1000)
def fib(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib(10000)) # 不会触发递归错误

内容的提问来源于stack exchange，提问作者LiamK469