Frame and the stack


#1

I couldn’t understand what Frame and the stack is.
I was wondering if someone can help me.


#2

If you follow the 'Looking at the frames in the debugger" section, you can actually see a stack of frames. I found it easier conceptually to call the singTheSong function with a lower number than 99 - say 5.
Try working out in your mind how the deeper frames got where they are and what you’d have to do to get them out again.
I stumbled across the down arrow - (next to the broken play type button described in the book section) that then took me the next few steps through the program- I could see the frames discarding from the stack and the older data rising to the top again. Recursion fell into place for me then too.


#3

The best way to understand recursion, frames and the stack is to think of it as a “Deck of Poker Cards”.

Every time a “Function is called” it puts a new frame on top of the stack (Kind of like putting one poker card on top of another).

So numberOfBottles will keep putting one frame on top of another starting at 99, then 98, and so on…

Note: If you don’t tell the function when to stop it will go on until infinity and can make your program crash i.e : 3, 2, 1, 0, -1, -2, -3, infinity…)

In this case frames keept going on top of each other UNTIL it reached the if statement that told it to stop when numOfBottles == 0.

if (numberOfBottles == 0) { printf("There are simply no more bottles of beer on the wall.\n");

Now that the if statement has been met, we have 99 frames stacked on top of each other (Kind of like having 99 poker cards one on top of the other).

From this point on the frames will start getting discarded one-by-one from the top of the stack all the way to the bottom of the stack (Like taking one Poker Poker Card off the Deck from top to bottom until you have no more cards left).

printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles);

In this case they will get discarded in the order in which they where placed so after 0 (zero), 1 was the frame (“card”) that was on the top of the stack (deck), then 2 was underneath it, then 3, and so on until 99 (because 99 is where we started and that is the last frame (poker card) that is on the very bottom of the stack (“deck”).

Once you reach 99 there are no more [b]frames/b left to discard, and your [b]stack/b is now empty, so there will be “no more bottles to put into the bin” and your program will finally end.

Hope this helps clear out the confusion.


#4

I think I’ve got the stack of cards idea, but when numberOfBottles==0 I don’t understand what makes the stack start to discard cards? All the function does is call printf with a different set of parameters, what actually makes the stack unwind? Looking at the code I sort of expected that “simply no more bottles” message to be the last thing to happen.

A little worried that I seem to have such major comprehension problems so early on :frowning:

David

#5

I’m also not to clear on why the “put a bottle in the recycling” print happens in the order that it does.

From looking at the function, you would think it would go like:

99 bottles of beer on the wall, 99 bottles of beer.


You take one down, pass it around, 1 bottles or beer on the wall.
There are simply no more bottles of beer on the wall.

end function

I just dont get why the last print keeps getting called when the if is true. What is incrementing the numberOfBottles?


#6

Read this post on recursion: viewtopic.php?f=137&t=5546 to see if it clears up the fog.


#7

I’ve read that post and to be honest no, it doesn’t really help, it seems very complicated to be honest! The whole thing feels to me as if it’s way too complicated an idea to introduce so early to people (well, me) for whom this is all new, and if it isn’t then I need a much more basic explanation of what is going on.

I seem to have hit a comprehension problem desperately early on, and that really has knocked my confidence for six.


#8

I’m not sure if this will help, but maybe this will make things a bit clearer:

5 bottles (one frame) -> Beginning of the function call (first frame is a the very bottom), Start printing: “# of bottles of beer on the wall”.
4 bottles (two frames)
3 bottles (three frames)
2 bottles (four frames)
1 bottle (five frames )
0 bottles (six frames on top of each other, this one being on the very top) -> if ( bottles == 0 ) end of function call.
1 Recycle (five frames ) - Now start recursion, singTheSong(oneFewer): "Start printing: Put a bottle in the recycling, # empty bottles in the bin."
2 Recycle (four frames)
3 Recycle (three frames)
4 Recycle (two frames)
5 Recycle (one frame) -> Last frame at the bottom of the stack, end of recycling bottles.

A great source for understanding how memory and the stack works is this one:
masters-of-the-void.com/book5.htm


#9

I’ve just hit confusion on this too, but if it helps, I think I figured it out. Here’s my explanation.

Each “card” or function on the stack hasn’t actually finished running, because the recursion kicks in before the end of the code, and places a new “card” or function above it in the stack which then takes precedence.

When the IF condition is met, that “top” card/function can complete. Then it is discarded, and the next one down picks up where it left off (after the recursion) to state:

printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles);

Once that printf code has run, that card/function finishes too, and pops off the stack. The next one repeats this, with ever increasing numbers.

It’s very, very clever and elegant once you understand it. One variable counts up as well as down, and a single function does the song, as well as the “clean-up”. But, yes, the explanation needs work.

Let me know if that helps. Hopefully it has.


#10

This really helped me a lot & I have my head around it now.