Recursion - printf("...recycling..")


#1

I’m trying to understand why the last printf(),

singTheSong(oneFewer); // This function calls itself! printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles);

doesn’t log till numberOfBottles = 0.

Hmm…it’s difficult to explain what I think is happening, but I’ll give it a shot.

Every time singTheSong() is called, a new frame is added to the stack. As a result the last printf() can’t execute till numberOfBottles = 0 and each stack frame is subsequently discarded. singTheSong() is blocking the printf(), correct?


#2

Thanks for that - I was wrestling with what was going on and how it “knew” how many bottles to recycle; popping each item of the stack is exactly what is happening.

It seems very contrived to me (although a good illustration of a stack!) - accumulating stacks in a recursive argument would seem to have the potential for eating memory. Or perhaps I’m being old fashioned!


#3

I’m still a bit confused by the BottleSong example though.

By moving my breakpoints around:
I understand that the frames are popping off the stack.
I understand that singTheSong doesn’t get called again after the count hits 0.

But why is it calling the recycling printf at all?

Once numberOfBottles gets to 0 would it not satisfy the if at the beginning and then just exit the function? Why is it going into the else block at all?


#4

The example was designed to make you come to grips with two facts:

  1. As each singTheSong() completes, it pops off the stack and the singTheSong() that called it resumes execution
  2. Each frame has its own numberOfBottles variable – and each one of them has a different value.

Does that help?


#5

[quote=“AaronHillegass”]The example was designed to make you come to grips with two facts:

  1. As each singTheSong() completes, it pops off the stack and the singTheSong() that called it resumes execution
  2. Each frame has its own numberOfBottles variable – and each one of them has a different value.

Does that help?[/quote]

Perhaps. Let me see if I can explain it correctly.

Each singTheSong() from 99 -> 1 is blocked when it calls singTheSong() and drops a new frame on the top of the stack.
Once we get the last bottle off of the wall and hit 0 that singTheSong() exits.
Each of the stacked up singTheSong() frames then pick up where they left off and complete their execution which is to again printf the bottles into the bin.

The more I think about it the more it makes sense. So I hope that’s what’s going on here!
Thanks!


#6

That is exactly how it works.


#7

In that case w00t good sir. w00t indeed!

Thanks.


#8

[quote=“AaronHillegass”]The example was designed to make you come to grips with two facts:

  1. As each singTheSong() completes, it pops off the stack and the singTheSong() that called it resumes execution
  2. Each frame has its own numberOfBottles variable – and each one of them has a different value.

Does that help?[/quote]

Perfect explanation. Definitely include that in the next revision! Enjoying the read!


#9

I had to actually set break points at each line of code to finally figure out what was going on.

First I changed the variable to 3 rather than 99 to save time:

int main (int argc, const char * argv[]) { singTheSong(3); return 0; }

I could then see how the stack was built up and then how the function, once it was finally allowed to follow through with the line:

could then work through the stack one piece at a time until the stack was exhausted, adding bottles into the recycling bin. The reason it went from 1 empty bottle back up to 99 is because of the last in, first out principle of how the stack is organized.


#10

Wow. I see now that I missed the point of this entirely, although I succeeded in doing the exercise and also in making another Command Line Tool which counted down from 99 (or whatever number one put in) bottles on the wall and up from 0 bottles in the bin at the same time, and was very proud of myself for doing a bit extra (see code below if interested). Is there any hope for people like me?

[code]//
// main.c
// BeerSongTwo
//
//

#include <stdio.h>

void singTheSong(int numberOfBottles, int recycledBottles)
{
if (numberOfBottles == 0) {
printf(“There are simply, absolutely NO MORE BOTTLES of beer on the wall.\n”);
printf(“Time to brew some more!\n”);

} else 
{
    printf("%d bottles of beer on the wall, %d bottles of beer. ...\n", numberOfBottles, numberOfBottles);
    int oneFewer = numberOfBottles - 1;
    int oneMore = recycledBottles  + 1;
    printf("We take one down, and share it around, %d bottles of beer on the wall.\n", oneFewer);
    printf("Put that bottle in the green recycle bin, %d empty bottles in the bin.\n", oneMore);
    singTheSong(oneFewer, oneMore);   //This function calls itself!
    
}

}
int main (int argc, const char * argv[])
{
singTheSong(99, 0);

return 0;

}

[/code]

Yvonne


#11

Bumping because I still can’t grasp the explanation provided here on this thread.

If the condition “numberofbottles == 0” is met, then the “ELSE” statement becomes obsolete, logically speaking. printf(“put a bottle…”) was never allowed to print because singTheSong(oneFewer) – which precedes it – recalls itself (it goes back to the top of the if statement). So once the condition is met, there is no need to go through the “ELSE” statement and thus the printf(“put a bottle…”) which was never given a chance to print, should disappear along with it.

So what am I not getting here? How is printf(“put a bottle…”) allowed to print when it was never given a chance to? It doesn’t seem to fit anywhere.

Please help guys! im on wits end! :smiley:


#12

I still do not see how the program went from 0 bottles then put them in the bin and counted back up again … can anyone explain this to me … is there some magic which makes it count from 0 back up to 99 again?

Constantly Confused …


#13

Suggestion: read through the older threads on the topic, particularly http://forums.bignerdranch.com/viewtopic.php?f=137&t=3200


#14

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.