Python nested vs chained function calls in recursion-CodePudding

I am wondering about the output

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

of code provided below.

What I am wondering about is: What causes that chaining of function calls compared to nesting of function calls has different impact on the by the counter counted calls to the topmost function starting the recursion? In other words, how does it come that nested calls don't reduce the depth of recursion like the chained calls do? All of the nested functions wait for their parameter being evaluated, so they should take space on the stack, but it seems that they don't.

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

CodePudding user response：

When you write

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

it's roughly equivalent to

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

Each of the argument function calls is completed before calling the next one in the chain, so they don't add to the recursion depth.

CodePudding user response：

In your second example, f2(f3(f4(f5(f1())))), python will evaluate the innermost expression first. That's the recursive call f1(). And since f1 calls f1 again, f2 and etc... are never called. Notice that only "f1" is printed.

If you disassemble f1, you'll see the byte codes

   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 calls the top thing on the execution queue. So first you get f1, then f2, etc... (well, if you ever get that far).

Python's "recursion count" is really a stack depth count. If it gets big, like 1000 calls big, that's likely a recursion problem, hence the name. In your first example, calls to f2, etc increase the stack count faster than f1 increases the count. But in your second example, because f1 calls f1 before any other funtion, cnt goes up at the same rate as the stack count.

The reason why you don't quite reach 10 is that there is already some stuff on the stack by the time your code runs.