Python中两个看似等价的递归函数为何递归深度差异显著？

我在本地测试发现，两个带记忆化的斐波那契递归函数触发最大递归深度的n值差异显著：

• 第一个函数在n=2960时触发限制：

m = {0:0, 1:1}
def f(n):
    if n not in m:
        m[n] = f(n - 1) + f(n - 2)
    return m[n]

• 第二个函数在n=988时就触发限制：

m = {0:0, 1:1}
def f(n):
    if n not in m:
        m[n] = sum(f(n - i) for i in [1, 2])
    return m[n]

核心差异：每一层递归的栈帧开销 #

Python的递归深度限制统计的是调用栈中所有未完成的函数帧总数，两个函数的本质区别在于递归过程中每一层产生的额外栈帧数量：

直接相加版本的栈行为 #

当计算f(n)且n不在缓存时，会先调用f(n-1)，这个调用会递归到f(1)。此时栈中只有f(n), f(n-1), ..., f(1)共n个未完成的函数帧。当f(1)返回后，f(n-2)已经被f(n-1)的计算过程缓存，会直接返回结果，不会产生新的递归栈。整个过程中，栈的最大深度等于n。

生成器sum版本的栈行为 #

使用sum(f(n-i) for i in [1,2])时，每一次调用f(k)（k≥2）都会产生两个额外的栈帧：sum函数的帧，以及生成器表达式的__next__方法帧。随后生成器迭代第一个元素时调用f(k-1)，而f(k-1)又会重复这个过程——创建自己的sum和生成器帧，再调用f(k-2)，直到f(1)。

此时栈的结构是：f(n) → sum → 生成器帧 → f(n-1) → sum → 生成器帧 → ... → f(1)。每一层f(k)都会额外增加2个栈帧，总栈帧数为n + 2*(n-1) = 3n-2。

当栈帧总数达到Python的递归深度阈值时，就会触发限制。假设阈值为L：

• 直接相加版本支持的最大n₁≈L
• 生成器sum版本支持的最大n₂≈L/3
  这就是你看到2960≈3*988的核心原因。

多求和项场景的推导 #

假设递归式为m[n] = sum(f(n-i) for i in 1..k)（k为求和项数量），结合记忆化机制：

• 直接相加版本：不管k是多少，最大n仍约等于栈帧阈值L。因为只有第一个求和项f(n-1)会触发完整递归链，后续的f(n-2)到f(n-k)都会直接读取缓存，不会产生新的递归栈，栈最大深度始终为n。
• 生成器sum版本：不管k是多少（只要k≥2），最大n仍约等于L/3。因为最大栈深度由第一个求和项的递归链决定，每一层f(m)都会额外产生sum和生成器两个帧，总栈帧数仍为3n-2，后续求和项的调用不会增加栈深度。

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