This was part of my assignment, a small function. Book asks what the output is, if N=1. I simply can't wrap my head around, why the function counts down after reaching N<3, when it adds 1 to N
Don't know if this is homework help, or just help, as the assignment has been submitted.

I added the silly comments, just to see where I'm at.

def F1(N):
    print(N, "First N")
    if (N < 3):
        print(N, "goin' in first time..")
        F1(N + 1)       #Prints N+1 = 2
    print(N, "Last N")

F1(1)

Output is:

1 First N
1 goin' in first time..
2 First N
2 goin' in first time..
3 First N
3 Last N
2 Last N
1 Last N

 

It's doing exactly what you are telling it to do.

When you call it the first time, N=1 and so it prints the first two line and then calls a function and once that function returns it prints the third line

#F1(1)
1 First N
1 goin' in first time..
#------------------------
execute F1(2) to completion
#------------------------
1 Last N

Executing F1(2) does the same thing

#F1(1)
1 First N
1 goin' in first time..
#------------------------
F1(2)
2 First N
2 goin' in first time..
#------------------------
execute F1(3) to completion
#------------------------
2 Last N
#------------------------
1 Last N

Executing F1(3) only prints the first and third lines and makes no function call.

#F1(1)
1 First N
1 goin' in first time..
#------------------------
#F1(2)
2 First N
2 goin' in first time..
#------------------------
#F1(3)
3 First N
3 Last N
#------------------------
2 Last N
#------------------------
1 Last N

Don't overthink it. It is no different than if you had

def fred():
print("Early Fred")
sue()
print("Late Fred")

You would expect the program to print out "Early Fred", then do whatever it is that sue() does, including printing out whatever sue() prints out, before printing out "Late Fred".

 

I tried your "Late Fred" function, and that behaves as I would have thought. I will accept this and stop thinking about it. It's just the counting down part, when there is no counting down part, that bothers me.

def sue(name2):
    print(name2)
    
    
def fred(name1):
    print(name1)
    sue(name2)
    print("Late Fred")

name1 = "So Sue Me"
name2 = "Penguin"    
    
fred(name1)

So Sue Me
Penguin
Late Fred

 

I tried your "Late Fred" function, and that behaves as I would have thought. I will accept this and stop thinking about it. It's just the counting down part, when there is no counting down part, that bothers me.

Don't give up just yet; recursion is one of those concepts that seems incomprehensible until it "clicks", and then it feels entirely obvious.

I think the key point you're missing is how the stack works. When a function is called, a section of memory called the stack is set up with everything the function needs to do its thing. Consider your second, non-recursive example, whose program flow you fully understand. You call the function fred, which -- behind the scenes -- causes a stack frame to be created with the value of name1 = "So Sue Me". Within that frame, you print name1 and then you call another function sue. This causes a different stack frame to be created with the value of name2 = "Penguin". Within this stack frame, name2 is printed and then the function returns. Where does it return to? The point in the code right after the point where you called sue: the stack frame that belongs to the fred function. Here, the string "Late Fred" is printed, and then the function fred returns. Where does it return to? The point in the code right after you called fred, which ends the program.

Now consider your recursive function. When you call F1 the first time, the stack is set up with the value of N = 1. You print some stuff and then call F1 again, which causes a different stack frame to be set up with N = 2. This continues, creating new stack frames, until the recursion reaches the base case of N = 3, which stops the recursion. Here's the critical part.

That final 'print(N, "Last N")' statement now runs in the last frame, which has N = 3, and so it prints "3 Last N". As that's the last statement in the function, the function returns. Where does it return to? To the point in the code right after the point where you last called F1, which is the stack frame with N = 2. Here, the final 'print(N, "Last N")' statement runs from this stack frame, and so it prints "2 Last N" and then returns. Where to? To the point in the code where this version of F1 was called. In this stack frame, N = 1 and so the the final 'print(N, "Last N")' statement executes with N = 1, showing "1 Last N" on the screen.

As this last stack frame was the first stack frame -- the first call to F1 -- the recursion is finished, all the stack frames have been resolved, and the program returns to the point after that "F1(1)" statement, ending the program.

The key idea is this winding and then unwinding of the stack. It's easy to forget that the 'print(N, "Last N")' statement doesn't get executed until the unwinding stage, which is why your program counts up and then down, even though a cursory glance suggests it should only count up.

Try a few different recursion examples and I'm certain you'll get the hang of it.

 

@bogosort you just blew my mind. Thank you very much! I will read more up on the stack and do some recursion. I tried one with infinite recursion, and I understood why that was so.

 

I tried your "Late Fred" function, and that behaves as I would have thought. I will accept this and stop thinking about it. It's just the counting down part, when there is no counting down part, that bothers me.

def sue(name2):
    print(name2)
   
   
def fred(name1):
    print(name1)
    sue(name2)
    print("Late Fred")

name1 = "So Sue Me"
name2 = "Penguin"   
   
fred(name1)

So Sue Me
Penguin
Late Fred

The "counting down" is an illusion. Each call of the function prints out the same value twice -- once at the beginning and once at the end. In the middle it either calls a function giving it a different value or it doesn't. That function does the same thing -- it prints the value it was given twice, once at the beginning and once at the end and, in the middle it either calls a function giving it a different value or it doesn't.

Try separating the notion of "counting up" and "counting down" from it by making that aspect random.

import random

call = 0

def F1(N):

    global call

    call += 1
    print("Call", call, "entry with N = ", N)

    if (N % 5 != 2):
        new_N = random.randint(10,30)
        print("Calling F1(", new_N, ")")
        F1(new_N)
    else:
        print("No call being made.")

    print("Call", call, "exit with N = ", N)
    call -= 1

F1(random.randint(10, 30))

Run this a few times. First run it until you get just a couple of calls to F1(). Then run it until you get a bunch of calls. Walk through the code for each case and see how it all works.

Remember that, except for the variable 'call', which is specified as being global, each call to F1 gets a block of memory for it's local variables, namely N, that is all it's own. The function doesn't have a single variable N, each instance of the function has its own variable N. This is done by storing a functions local variables on the a stack and each call to the function gets a new stack frame allocated with a new set of variables. When that function returns, that stack frame goes away and the stack frame of the function that called it is re-exposed so that when the caller takes back over it has it's local variables accessible again. The mechanics are identical whether fred() calls sue(), or fred() calls fred(). There is NOTHING special about recursion as far as the program execution is concerned as soon as you are using a stack-oriented program architecture.

 

Thanks for the exercise @WBahn I will try that. I am in the midst of studying for another exam right now, so recursion will be put on hold for a few days.

Again, thanks for the stack tip, makes so much more sense now, though I probably don't understand it 100%, it helped me see it in another way.