If vs While or Recursion just kicks my ass

[Carol Murphy]

These two loops act very differently, and I can't figure out why.

def sqspin(num):    if num > 0:        print(num)        sqspin(num-1)         sqspin(5)

def sqspin(num):    while num > 0:        print(num)        sqspin(num-1)         sqspin(5)

The if block terminates but the while block does not. Both print the count down from 5 to 0 for the value of num,
but the while loop continues printing zeros for ever.
Is there a guru around who can explain what in the Sam Hill is going on here?

[Piet Souris]

hi Carol,

have a look at sqspinWhile.

After the recursion, when coming back into the 'while' loop, that variable 'num' is unchanged, so the while loop goes on, and on, and on, and .... Why does 'sqspinIf' not suffer from ths problem?

[Carol Murphy]

I can't see where the problem is. Both if and while test for num > 0, and they both decrement num as the end of each loop, so why do they act differently?
Once the condition becomes false, don't they both exit? I'm missing something really obvious here.
I'm sure it has to do with the recursive call and what happens when the calls go up the stack, but I'm not understanding it.
Okay, I think I get it. The recursive call doesn't return a value, so in the if loop, once num > 0 becomes false, the calls just
return none until the program exits.
The while loop keeps testing the value of num > 0, so when it returns none and continues calling up the stack, it gets hung
up on num = 1, which keeps it cycling back to zero. Right???
Okay, NOW my question is this: Why doesn't a while loop fall through? Why does it go back to the conditional line? That doesn't make any sense.

[Joe Ess]

Carol Murphy wrote:they both decrement num as the end of each loop, so why do they act differently?

Well, "if" and "while" are used for different purposes.  If tests a conditional once.  While will loop until a condition becomes false.  Let's try tracing what happens in both code samples.  With a starting value of 2, the execution of the "if" version looks like so:

Stack depth 0
sqspin invoked with num = 2
if num > 0 is true
print num
invoke sqspin (1)
    Stack depth 1
    sqspin invoked with num = 1
    if num > 0 is true
    print num
    invoke sqspin (0)
        Stack depth 2
        sqspin invoked with num = 0
        if num > 0 is false 
        sqspin(0) returns
    sqspin (1) returns
sqspin (2) returns

Try the same with the "while" version.

[Carol Murphy]

If tests a conditional once.  While will loop until a condition becomes false.  

I think my misunderstanding begins here, with what happens once the condition becomes false. If returns up the stack without testing the values against the condition.
While will continue to check sqspin(num) against the conditional using the value of num returned by sqspin(1), thus causing a never-ending loop, because of the recursive call.

I tried running these both in Python Visualizer, and from what I could see they behave the same until they start returning up the stack.
I'm not able to visualize this statement:   "While will loop until a condition becomes false. "

What I see happening is the while looping until the condition becomes false, then stopping, then looping again if the condition becomes true when used in a recursive function.

I have always had the idea in the back of my mind that while and if worked pretty much the same way, and this makes me feel confused. Am I understanding this correctly?

I have another question about the way recursion works. Lines 8-9 & 10-11 are duplicates of each other, so 1 would be printed twice. When the program runs the numbers are printed
in descending order until 0 is reached, then they stop. The program continues running until the calls on the stack return, but nothing more gets printed.  Is there any significance
to lines 8-11 in the code you posted? Why the duplication if no number is being printed?

[Joe Ess]

Carol Murphy wrote:
Lines 8-9 & 10-11 are duplicates of each other?

They shouldn't be.  I have corrected my post.  

What I see happening is the while looping until the condition becomes false, then stopping, then looping again if the condition becomes true when used in a recursive function.  

What you are seeing the condition at one stack level becoming false.  The condition at the higher level never becomes false.  This is something you will probably miss stepping through code in a debugger, but should be able to see if you traced the code as I did.

[Carol Murphy]

Thanks for the explanation Joe! I never learned to trace code. I think I need to focus on this for a bit.

[Tim Holloway]

If I'm not mistaken, you're confused about scope.

As a function argument, a new "num" is created for each call of the method. This instance of "num" is completely independent of all the other "nums" - specifically the ones in the stack of recursive calls. So changing a "num" at the bottom of the stack won't change the values of the "num"s at bottom-1, bottom-2, etc. and therefore the while loop would never terminate, since if "num" was passed as a value of 5, it would remain 5 forever, regardless of what subroutines (recursive or not) did. Only a change at the same call level would make any difference.

[Carol Murphy]

Hi Tim! You are correct, but I think I'm confused about more than just scope. The whole concept of how the stack works during recursive functions ties my brain into a knot. (Picture Twister with brain cells instead of arms and legs.)
I'm having difficulty picturing how and why an if statement just returns back up the stack, but a while loop gets stuck in this endless recursion.
I can understand the mechanics of something once I can picture how it works. Trying to get a mental picture of how a bobbin works to make stitches on a sewing machine is a good example.
I want to know that I truly understand what is happening before I feel comfortable using something. And I'm really struggling with the difference between the way an if statement and a while loop function once the condition has become false inside a recursive function. This is going to keep me up a few nights, I think!

[Tim Holloway]

Well, see the "if" statement doesn't return up the stack. It executes. And then control goes on to the next statement. Since there's no next statement in the code, the next statement in Python is assumed to be a "return" statement returning nothing.

The loop statement, on the other hand, never gets to the next statement, because it's still looping. Because the loop termination condition is always false, since "num" never changes (regardless of what nums in recursive calls did). So, no next statement, no implicit return.

A stack is just a pile of stuff. When most modern programming languages execute a procedure, function or method call, the stack is where the return address of the calling code is placed, then all of the function-local variables and the method arguments are piled on top of it. Call a sub-function, the same thing happens again. Do a "return" and the local variables are popped off the stack and the return address is likewise popped and the program execution proceeds at that address. The exact contents and arrangements of the stack data vary depending on the language and the hardware (IBM mainframes like the System/360 had no stack instructions and had to fake it). But the context for a called method is known as a stack frame and contains everything you need to restore variables, machine registers, etc. when you jump out of one chunk of code and into another. The process of popping off multiple frames is known as unwinding. It's done when an Exception is thrown and execution percolates rapidly back up to whatever method set up a "catch" for that exception (with occasional diversions to execute "finally" code).

The execution model for modern programs is basically calls all the way down with the Main program being "called" by the Operating System (or the virtual machine in cases like Python and Java). So every method that's called has a stack frame, even the Main method. Usually, the active method has a pre-allocated frame so that the method variables don't actually get stored when a sub-method is called because their memory is already allocated in the current frame. Although anything that's in a virtual or actual machine register will get stored before the call is taken.

Languages like Java have basically 2 types of memory - stack frame memory and heap memory (allocated via the "new" operator). Python also has something resembling old-fashioned static memory, which was generally a block of storage allocated when the program started. Java doesn't have that, since all memory in Java is object-based, not hanging around in some sort of  global  or module-local variable-space.

[William Ng]

The thing about recursion, and this is what gives it its magic, is that it invokes itself in its body. People have the hardest time understanding this concept and get their minds tied in knots trying to figure it out. It's not that hard once you do figure it out. An important part of understaning this is to remember that it is a method. Now refereing to your code, you never modify the variable num. So each time that the method is called, num remains the same, except when it is passed to the call on itself, which is the correct way to implement recursion.

The problem you have with the two versions is simple if you know how if and while works. The body of an if is escuted at most once. While, on the contrary, can be executed none, however many times until the condition is no longer valid, or, if you are unlucky enough to make such a vile error, an infinite number of times (The dreaded infinite loop).
So, you know that the first version is a good kid and does what it's supposed too. Lets look at the bad kid.
It will pretty much behave in the way that the if does for a a while. It will enter the body, check the condition, then since it is true it will end up printing, then calling itself. It does so until the condition is no lonber valid when it calls itseld. This condition is when num is less than 0.  So cycles back to '1. I ran the while version, and it looks like it is printing not 0's, but 1s. What platform are you using? Do they interpret 0s as 1s.

[Carol Murphy]

The loop statement, on the other hand, never gets to the next statement, because it's still looping.  

And this seems strange to me. Why doesn't the loop stop once the condition has become false. As the calls return up the stack, why do
they test the conditional again? Or do they even test it again? Do they simply continue running from where they left off, since there is no
explicit return, and therefore cause the loop to pick up where it left off, thus becoming eternal?  If I was prone to paranoia, I would assume
while loops were designed simply to drive me mad..........

 I ran the while version, and it looks like it is printing not 0's, but 1s. What platform are you using? Do they interpret 0s as 1s.

You are correct, Mr Wu! The version of the code I was using before had print(num) before the loop, but in the code I posted here I had moved it inside
the loop.

I think I'm close to grasping this concept, thanks to your input. (The folks at StackOverflow tend to indulge in snark, which renders their form of help rather unhelpful.)
The main thing I will take away from all of this: avoid while loops in conjunction with recursive function calls to avoid falling down rabbit holes!