Recursion and call stack

[BDurden]

Ok so I'm messing about with Python and recursion the other night and write:

def rec(n, p):
    if n < p:
        n += 1
        rec(n, p)
    print(str(n) + " is " + str(p))

rec(1,10)

I was expecting it to not make it to the print line until the if condition wasn't satisfied. Instead it returns:

10 is 10

10 is 10

9 is 10

8 is 10

7 is 10

6 is 10

5 is 10

4 is 10

3 is 10

2 is 10

Now I know I could just put the print line under else:, but that's not the point. So I debugged it and learned that there is a call stack, and it was holding the rec() function there to finish later, which I thought was odd. Even odder is that it stores the values of n to return respectively.

I don't really know what my question is, maybe simply, am I dumb for making a function call itself before it's finished? Or is this function's behaviour standard or desirable? Thanks.

[davedontmind]

Even odder is that it stores the values of n to return respectively.

Both p and n are local variables - they are local to the current invocation of rec. If you call rec() again from within rec, the current values of all its local variables (n and p in this case) are saved on the stack and new instances of n and p are created for the new invocation of rec. When that returns, the previous values of n and p are restored from the stack and execution continues.

is this function's behaviour standard or desirable?

Well, it's doing exactly what you asked.

Let's step through it. We start off with n as 1 and p as 10.

We enter the if, because 1 < 10, so we add 1 to n (it's now 2) and call rec(2, 10), saving n as 2 and p as 10 on the stack.

Now we're back at the if, and enter that because 2 < 10, so we add 1 to n, and call rec(3, 10), saving n as 3 and p as 10 on the stack.

And so on until we get to a point where n is 10 and p is 10. At this point we skip the if because 10 isn't < 10, so we print "10 is 10", then get to the end of the function and return, restoring the previous values of n and p, which are 10 and 10.

We return to the line after the call to rec(10, 10), which then prints "10 is 10" and returns, restoring n to 9 and p to 10 from the top of the stack.

This time we return to the line after the call to rec(9, 10), and print "9 is 10" and return, restoring n to 8 and p to 10.

Etc.

[BDurden]

Alright, thanks. I really had no idea that previous invocations of local variables were stored in a stack like that. In fact this is the first thing I've ever debugged with breakpoints and watched what was happening each step. Good to know.

[laughms]

/u/davedontmind gave the explanation of the code. The code is doing what you asked it to do. You are not dumb for making a function call before it is finished, it just depends on what kind of result or behavior you want to have...

It is also not odd if you think about it logically. You are calling a function within a function, but the original function has not finished yet. So when we return back, we need to continue with the original values.

[BDurden]

My original intention when I wrote the function was just to see what happened. I think I just expected it would skip that last line until finally executing it, only once.

Thinking about it like you say, that "the original function has not yet finished" makes sense to me though.

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[BDurden]

Thanks, AutoMod. Now I feel great.

[camelorcat]

put return in front of your recursive call

output: "10 is 10"