Looking for explanation of what's happening in this recursive Python snippet?

Question

The snippet:

def fun(a):
        if a > 30:
            return 3
        else:
            return a + fun(a+3)
print(fun(25)) # prints 56

Now my question is this: The return from the function does not seem assigned specifically to a. So how does the program ever reach the a > 30 branch, and terminate?

In practice, the snippet prints 56. How does the function arrive at this value? One answer seems to be: the return value of fun(a+3) is indeed assigned to a, resulting in a becoming 53 i.e. (25 + (25 + 3)) on the first pass and 56 i.e. (53 + 3) on the next pass.

I tried:

def fun(a):
        if a > 30:
            return 3
        else:
            return fun(a+3)
print(fun(25))

And got 3. So a + fun(a + 3) should return 28 to the print command.

Remember that each call has its own scope. Calling `fun(a+3` calls `fun` with a value that gets assigned to a _new variable_ called `a` scoped to that new function run. It's not "the same `a` the whole time". — Mike 'Pomax' Kamermans, May 17 '23 at 04:13
Your second function will return 3 no matter what (subjected to recursion limits) - because `fun` will eventually call itself with an argument `a` that satisfies `a > 30`, and that value will be returned all the way back up the recursive call stack - `fun(-2960)` will be within the default recursion limits while `fun(-2961)` will exceed it. — metatoaster, May 17 '23 at 04:28
`fun()` is recursive. It actually gets called 4 times (not 2). Each time it gets called in `else: return a + fun(a+3)`, the argument to `fun()` is _increased_ by adding 3 to its value for `a`. So eventually, the argument is larger than 30. Imagine that all the previous calls are "stuck" in their own `else: return a + fun(a+3)` line. Now that in the last level, the argument is larger than 30 tha level returns 3 but each upper level, one by one, returns `a + [lower level result]`, "finishing" its `else: return a + fun(a+3)` line. — emno, May 17 '23 at 04:43
@emno Your comment "each upper level, one by one, returns a + [lower level result]" was what clarified the issue. Thank you. — Nathan, May 18 '23 at 06:06

score 0 · Answer 1 · answered May 17 '23 at 04:32

Because of the recursive call to the function fun(), when you pass it the initial input=25, it calls the same function with input=28 and then with input=31 at which point it exits the function since input > 30. But the retuned value is not 3 due to the order the python call stack is unloaded.

You can use the "pythontutor" website to visualize how the call stack is used in python call execution. Just copy paste your code at Python Tutor and click the "Visualize Execution" button. As you iterate through the statements one by one using "Next", it will show you the detailed path to how the function ends up returning 56.

The point about the Python call stack added a new element to my understanding. Thank you, — Nathan, May 18 '23 at 05:49

Kache · Accepted Answer · 2023-05-17T04:43:14.397

One way to explain and visualize what's happening is with print debugging.

With the additional print() calls added (and lvl to track each level of recursion):

def fun(a, lvl=0):
    print("  " * lvl, f"fun({a}, {lvl})", end="")
    if a > 30:
        print(" => 3")
        return 3
    else:
        print(f" => {a} + fun({a + 3}, {lvl + 1})")
        return a + fun(a + 3, lvl + 1)

print(fun(25)) # prints 56

You'll see the following output breaking it all down:

❯ python foo.py
 fun(25, 0) => 25 + fun(28, 1)
   fun(28, 1) => 28 + fun(31, 2)
     fun(31, 2) => 3
56

Because 25 + 28 + 3 = 56

Each line represents one call of the same function, each with its own independent scope. The variable a never gets assigned to nor shared between these calls/scopes.

Looking for explanation of what's happening in this recursive Python snippet?

2 Answers2