CODEWITHSUNDEEP
pythonrecursion
user7711283
user7711283

Reputation:

Python nested vs chained function calls in recursion

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

Upvotes: 0

Views: 80

Answers (2)

tdelaney
tdelaney

Reputation: 77407

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

The byte code executor has its own stack. Some byte codes put things on the stack, some take things from the stack and replace them with some resulting value. Here, all of the functions are loaded onto the stack and then a series CALL_FUNCTION byte codes pop and call the top thing on the stack. First f1, then f2 and etc.

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.

Upvotes: 0

Barmar
Barmar

Reputation: 782693

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.

You only add to the recursion depth when the body of a function calls another function. So you get recursion when f1() calls f2(), f2() calls f3(), ... and f5() calls f1(). Since this is infinite recursion, the initial f1() call never completes, so none of the chained calls happen, either.

Upvotes: 2

Related Questions