Python 标准库中的 lru_cache 能让递归函数复用已经计算过的结果，但它并不是无代价的。它会在原函数外层再包一个 wrapper，每一次缓存未命中的递归调用都必须先经过 wrapper，再由 wrapper 进入原函数。对深度递归来说，这个额外的调用层会迅速放大栈帧数量。假设普通递归某一时刻占用 N 个栈帧，使用 lru_cache 后，同样的逻辑在执行到第 N 层时，调用栈上会同时保留包装器帧和原函数帧，实际占用的栈空间接近普通递归的两倍甚至更多。栈空间是有限的，提前耗尽就表现为 RecursionError。
一、装饰器包装让每个递归层级多出一次调用
Python 函数调用会在调用栈上分配栈帧，栈帧里保存局部变量、参数、返回地址和临时表达式结果。递归越深，栈帧越多。Python 默认递归限制由 sys.getrecursionlimit() 控制，通常是 1000，也就是当调用栈中的帧数超过这个阈值时，解释器会抛出 RecursionError。普通递归只维护用户函数自身的栈帧，栈帧数量与递归深度基本一致。
加入 @lru_cache 后，模块里的函数名不再指向原始函数，而是指向缓存的包装函数。包装函数先做参数哈希和缓存查找，未命中时才调用原始函数。原始函数内部再调用同名函数时，又进入包装函数。于是每个递归层级至少包含一个包装函数调用和一个原始函数调用。在 CPython 的 C 加速路径中，包装层可能不直接对应 Python 栈帧，但仍会占用真实 C 调用栈；在纯 Python 实现或部分运行时中，包装层就是一个额外的 Python 帧。无论哪种情况，每层递归的实际栈消耗都比普通递归更大。
换句话说，lru_cache 并不会消除递归调用，它只是把缓存逻辑插进递归路径里。对于深层线性递归，缓存很少命中，这些包装成本不会因为复用结果而被抵消，反而会加速栈空间的耗尽。
from functools import lru_cache
# 普通版
def plain_fib(n):
if n < 2:
return n
return plain_fib(n - 1) + plain_fib(n - 2)
# lru_cache 版
@lru_cache(None)
def cached_fib(n):
if n < 2:
return n
return cached_fib(n - 1) + cached_fib(n - 2)
二、实验：普通递归与 lru_cache 递归的最大深度对比
为了更直观地观察差距，可以不用斐波那契而用一个线性递归函数，例如对 1 到 n 求和。线性递归不会有重复子问题，因此 lru_cache 的缓存命中率为 0，每次递归都走完整的包装调用路径，能体现最坏情况下的栈消耗。
import sys
from functools import lru_cache
sys.setrecursionlimit(2000)
def plain_sum(n):
if n == 0:
return 0
return n + plain_sum(n - 1)
@lru_cache(None)
def cached_sum(n):
if n == 0:
return 0
return n + cached_sum(n - 1)
for name, fn in [("plain", plain_sum), ("cached", cached_sum)]:
max_n = 0
for n in range(1, 2000):
try:
fn(n)
max_n = n
except RecursionError:
break
print(name, max_n)
在 CPython 3.11 左右的运行结果通常显示，plain_sum 可以递归到接近 sys.getrecursionlimit() 的深度，而 cached_sum 大约只能跑到该值的一半到七成左右，具体比例取决于 Python 版本和底层实现。差距来自两点：其一，每个递归层多出包装调用，实际栈占用更大；其二，包装层里还要维护缓存键、锁和缓存字典操作，单层占用的内存也比纯函数帧更大。
对于斐波那契这类重复子问题很多的递归，缓存命中后不会再进入原始函数，可能局部减少栈帧数量，但这不改变线性递归或首次计算路径上的额外开销。当递归问题是链式结构时，缓存几乎不会命中，栈深度直接受包装层拖累。因此出现 RecursionError 时，不一定是逻辑错误，而是栈消耗被装饰器放大。
三、避免方案：从递归改写、手动缓存到动态规划
最简单的方法是调用 sys.setrecursionlimit(10000) 把阈值调大。这在测试和小规模数据中有效，但属于临时方案。线程栈大小是操作系统决定的，递归限制调得过大可能触发 C 栈溢出，导致 Python 进程直接崩溃，而不是抛出可以捕获的异常。生产环境中不建议依赖过高的递归限制。
import sys sys.setrecursionlimit(100000)
最稳妥的方法是改成迭代。大部分线性递归都可以直接转换成循环。迭代只保留固定数量的局部变量，不会随 n 增加栈帧，因此从根本上回避了递归深度问题。比如求和和斐波那契都可以写成简单循环。
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def sum_iter(n):
total = 0
for i in range(1, n + 1):
total += i
return total
如果必须保留递归，可以手动维护缓存字典，减少包装层。手动缓存把字典存在函数外部或通过参数传递，递归调用仍然存在，但调用栈中只有用户函数自身，不会额外增加 lru_cache 包装帧。相比装饰器方案，同样大小的栈空间可以支持更深的递归。它的缺点是代码略繁琐，需要自己处理缓存键和并发控制。
_cache = {}
def fib_manual(n):
if n in _cache:
return _cache[n]
if n < 2:
value = n
else:
value = fib_manual(n - 1) + fib_manual(n - 2)
_cache[n] = value
return value
对于有最优子结构的问题，建议自底向上动态规划。动态规划直接按规模从小到大计算，不需要递归回溯。比如斐波那契可以用滚动变量保存中间结果。这样既得到缓存复用的好处，又没有递归栈压力。只有在递归结构天然清晰、且深度可控时，才建议保留递归加缓存的写法。
def fib_dp(n):
if n < 2:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
lru_cache 依然是非常有用的工具，在浅层递归或重复计算密集的场景中收益明显。只要认识到它的包装层会增加栈帧数量，就能在遇到 RecursionError 时快速判断是递归逻辑问题还是装饰器带来的栈开销。深度递归场景优先选迭代或动态规划，才是更可靠的工程选择。