递归中的 Python 嵌套函数调用与链式函数调用

Question

我想知道输出

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}') # 200
# RecursionError: maximum recursion depth exceeded
print('# -----------------------------')
#"""
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}') # 996
# RecursionError: maximum recursion depth exceeded

Answer 1

当你写的时候

f2(f3(f4(f5(f1()))))

大致相当于

temp1 = f1()
temp2 = f5(temp1)
temp3 = f4(temp2)
temp4 = f3(temp3)
f2(temp4)

每个参数函数调用在调用链中的下一个参数函数调用之前完成，因此它们不会增加递归深度。

仅当一个函数的主体调用另一个函数时，才会增加递归深度。所以当f1()调用f2()时，你会得到递归，f2()调用f3()，...和f5()电话f1().由于这是无限递归，因此初始f1()调用永远不会完成，因此也不会发生任何链式调用。

Answer 2

在你的第二个例子中，f2(f3(f4(f5(f1()))))，python 将首先计算最里面的表达式。这就是递归调用f1()。而且由于f1再次打电话给f1，f2等等......从不被召唤。请注意，仅打印"f1"。

如果反汇编f1，您将看到字节码

7          20 LOAD_GLOBAL              2 (f2)
22 LOAD_GLOBAL              3 (f3)
24 LOAD_GLOBAL              4 (f4)
26 LOAD_GLOBAL              5 (f5)
28 LOAD_GLOBAL              6 (f1)
30 CALL_FUNCTION            0
32 CALL_FUNCTION            1
34 CALL_FUNCTION            1
36 CALL_FUNCTION            1
38 CALL_FUNCTION            1
40 POP_TOP

字节码执行器有自己的堆栈。一些字节码将东西放在堆栈上，一些字节码从堆栈中取出东西并用一些结果值替换它们。在这里，所有函数都加载到堆栈上，然后弹出一系列字节码CALL_FUNCTION并调用堆栈上的顶部。首先f1，然后f2等。

Python 的"递归计数"实际上是一个堆栈深度计数。如果它变大，比如 1000 个调用大，那很可能是一个递归问题，因此得名。在第一个示例中，调用f2等增加堆栈计数的速度快于f1增加堆栈计数的速度。但在第二个示例中，由于f1调用f1在任何其他功能之前，因此cnt以与堆栈计数相同的速率上升。

你没有完全达到 10 的原因是，当你的代码运行时，堆栈上已经有一些东西了。