递归中嵌套与链式函数调用的递归深度差异原因探究

问题 #

为什么递归场景下，链式函数调用和嵌套函数调用对顶层起始函数f1的调用计数差别这么大？明明嵌套调用时所有函数都要等参数求值，理论上应该占用栈空间，但实际却没像链式调用那样快速消耗递归深度？

运行输出 #

sys: maxRecursionDepth = 10
f1, f2, f3, f4, f5, f1, 
 >>> maxRecursionDepth =  2
# -----------------------------
sys: maxRecursionDepth = 10
f1, f1, f1, f1, f1, f1, 
 >>> maxRecursionDepth =  6

相关代码 #

链式调用实现 #

from sys import getrecursionlimit, setrecursionlimit
setrecursionlimit(10)
print(f'sys: maxRecursionDepth = {getrecursionlimit()}')
cnt = 0
def f1():
    global cnt
    print('f1', end=', ')
    cnt += 1
    f2()
def f2():
    print('f2', end=', ')
    f3()
def f3():
    print('f3', end=', ')
    f4()
def f4():
    print('f4', end=', ')
    f5()
def f5():
    print('f5', end=', ')
    f1()
# ---
try:
    f1()
except RecursionError:
    print(f'\n >>> maxRecursionDepth =  {cnt}')

嵌套调用实现 #

from sys import getrecursionlimit, setrecursionlimit
setrecursionlimit(10)
print(f'sys: maxRecursionDepth = {getrecursionlimit()}')
cnt = 0
def f1():
    global cnt
    print('f1', end=', ')
    cnt += 1
    f2(f3(f4(f5(f1()))))
def f2(f):
    print('f2', end=', ')
    f(f3)
def f3(f):
    print('f3', end=', ')
    f(f4)
def f4(f):
    print('f4', end=', ')
    f5()
def f5(f):
    print('f5', end=', ')
    f1()
# ---
try:
    f1()
except RecursionError:
    print(f'\n >>> maxRecursionDepth =  {cnt}')

核心原因分析 #

1. 链式调用的栈消耗逻辑 #

链式调用是线性栈累积：f1调用f2，f2调用f3，直到f5回调f1。每一次函数调用都会在调用栈中新增一个栈帧，且这个帧会一直保留到后续函数执行完毕才会弹出。

比如第一次调用流程：f1(栈深1) → f2(2) → f3(3) → f4(4) → f5(5) → f1(6)，此时栈深度已经到6；第二次进入f1后继续调用f2，栈深会快速涨到7、8、9、10，再调用f1就会触发递归限制报错。这就是为什么f1只被调用2次就触发错误。

2. 嵌套调用的栈行为本质 #

嵌套调用的关键在于Python的参数求值规则：调用函数时，会先完全求值所有参数，再创建该函数的栈帧并执行函数体。

看嵌套调用里的f1逻辑：执行到f2(f3(f4(f5(f1()))))时，会从最内层的f1()开始求值：

• 初始f1（cnt=1）要调用f2，先得求f2的参数f3(f4(f5(f1())))，于是先调用最内层的f1()（cnt=2）
• 这个新的f1()又要执行f2(f3(...))，同样先求值参数里的f1()（cnt=3）
• 以此类推，每一次f1的调用都会优先触发下一层f1的参数求值，而f2/f3/f4/f5的栈帧根本没机会被创建——因为参数还没求值完，这些函数从未被真正调用过。

此时栈中只有f1的调用帧，没有其他函数的帧占用额外空间，所以f1可以被调用6次才触发栈深度限制。你之前以为嵌套调用会占用更多栈空间，是误以为f2/f3等已经被调用，但实际上它们连栈帧都没生成，自然不会消耗递归深度。

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