0

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
Improve this question

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

15 Comments

Sorry, but I don't understand the explanation. temp2 = f5(temp1) should result in an attempt to run f5 with the parameter temp1. But f5 is not run so it can't be completed. *What do you exactly mean with *function call is completed?"" In my eyes none of the function calls is 'completed' waiting in the chain for execution ... Hmmm ... I will check it out in case of going out of recursion without bumping into RecursionError.
It's completed when the function returns. If the function raises an exception, it doesn't complete, and none of the rest of the calls will happen.
But the point is that these chained calls don't add to the recursion depth. You only get extra depth when the function calls another function itself.
> In 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 actually called, so they could not complete. If there is no RecursionError after f1 exits regularly all of the nested f2,f3,f4,f5 are executed the number of times f1 was run. But the calls to them seem to be stacked elsewhere not on the recursion stack. Where???
I'm just answering the question of why chained calls are different. What happens inside f1() is irrelevant to this.
|
0

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.

Improve this answer

2 Comments

After f1 is modified to exit e.g. at depth 4 with no RecursionError all of the nested f2,f3,f4,f5 are executed the number of times f1 was previously run. But the calls to them seem to be stacked elsewhere not on the recursion stack. Please provide in your answer also the explanation where are all these calls stacked for later execution? It can't be in the compiled code itself as the code can't know how many times the f1 will be run. And it seems not to be the stack with the call frames ...
Added explainer. There is indeed a second stack controlled by the byte code executor that holds temporary values about to be consumed by future byte codes. "add" for instance, would push 2 values to add, then BINARY_ADD would pop those two values and push the result of the add.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.