BeerSong / Recursion Confusion


#1

With the BeerSong tool, I get what’s happening up until the program prints “There are no more bottles…”. I’ve read through the other forum posts on this same topic, and am still not getting it.

As someone else asked, why, when there are 0 bottles, and the if conditional statement finally gets fulfilled, doesn’t the program end? How/Why does the program decide to kick back into the last printf statement about recycling inside of the ‘else’ conditional?

AND how/where is the program deciding to start counting up bottles in the recycling? Where is the math for that apparent addition defined?

Any help would be very appreciated.

Last question - if I got through the Challenge on Ch. 5 quickly, should I be worrying about not understanding all of the BeerSong tool at this point?


#2

Recursion is a little confusing the first time you see it. You’ll want to know it someday, but nothing in the rest of the book relies upon an understanding of recursion. Just keep going.


#3

Thanks Aaron. I’ll keep moving along then…


#4

The program doesn’t end because we put in a breakpoint. Did you remove it, as described in the 2nd paragraph on page 37?


#5

Dear Aaron,

I would really appreciate it if you quickly answer the questions mentioned - I am sorry I can’t settle for I would know it someday, right now I stepping into the code with the debugger but I am so confused.

when 0 bottles was reached, in the if statement it should have never entered into the else part(???) and how its counting up and the only math we have is subtracting. Please advise.

why, when there are 0 bottles, and the if conditional statement finally gets fulfilled, doesn’t the program end? How/Why does the program decide to kick back into the last printf statement about recycling inside of the ‘else’ conditional?

AND how/where is the program deciding to start counting up bottles in the recycling? Where is the math for that apparent addition defined?


#6

I was confused in exactly the same way here.

Essentially what is going on is each frame’s execution is blocked. Once the count hits 0 the previously blocked frames complete.

Take a look at this link for our discussion on it. http://forums.bignerdranch.com/viewtopic.php?f=137&t=3042


#7

first, I appreciate your help & time,

I think I kinda get it now, thats why the numberOfBottles starts from one, because the value on the top stack was 1?

did I get it or I am far off?


#8

You’ve got it, I believe.

In general, it’s good to simplify as much as possible when trying to understand what’s going on. So here are a few simple illustrations of how the code flows.

Simplest case: main calls singTheSong with 0 as an argument
main
singTheSong(0);

singTheSong:0
printf(“There are simply no more bottles of beer on the wall.\n”);

main
return 0;

Next simplest case, main calls singTheSong with 1 as an argument
main
singTheSong(1);

singTheSong:1
printf("%d bottles of beer on the wall. %d bottles of beer.\n", 1, 1);
int oneFewer = 1 - 1;
printf(“Take one down, pass it around, %d bottles of beer on the wall.\n”, 0);
singTheSong(0);

singTheSong:0
printf(“There are simply no more bottles of beer on the wall.\n”);

singTheSong:1
printf(“Put a bottle in the recycling, %d empty bottles in the bin.\n”, 1);

main
return 0;


#9

For those with a math background here is a variation on the beer song which can be used on really really long car or bus trips.

Aleph-naught bottles of beer on the wall,
Aleph-naught bottles of beer.
Take one down and pass it around,
Aleph-naught bottles of beer on the wall.

It can be easily implemented by a simple loop: while ( 1 ) { … }

(See: en.wikipedia.org/wiki/Aleph_number)


#10

The following explanation of what is happening when singTheSong() is called with 0 and 1 as arguments is confusing me. In this explanation, I notice that when singTheSong(1) is called it yields different results. The first time singTheSong(1) is called, it prints out "1 bottle of beer on the wall… etc. However the second time singTheSong(1) is called it prints out "Put a bottle in the recycling… etc. Why wouldn’t singTheSong(1) always produce the same result when given 1 as an argument?

Here is the explanation I’m referring to:

Simplest case: main calls singTheSong with 0 as an argument
main
singTheSong(0);

singTheSong:0
printf(“There are simply no more bottles of beer on the wall.\n”);

main
return 0;

Next simplest case, main calls singTheSong with 1 as an argument
main
singTheSong(1);

singTheSong:1
printf("%d bottles of beer on the wall. %d bottles of beer.\n", 1, 1);
int oneFewer = 1 - 1;
printf(“Take one down, pass it around, %d bottles of beer on the wall.\n”, 0);
singTheSong(0);

singTheSong:0
printf(“There are simply no more bottles of beer on the wall.\n”);

singTheSong:1
printf(“Put a bottle in the recycling, %d empty bottles in the bin.\n”, 1);

main
return 0;


#11

Good question. It’s not that singTheSong(1) is being called twice; rather, it’s called just once, but it is suspended when singTheSong(0) is invoked, and resumes once that completes.

If it helps to conceptualize what’s happening, pretend (or actually rename) singTheSong for the base case of 0 to something else, like “songIsEnding”.

So singTheSong(1) calls songIsEnding(), and when the latter is done, singTheSong(1) picks up where it left off.


#12

I didn’t understand the last part : printf(“Put a bottle in the recycling, %d empty bottles in the bin.\n”, numberOfBottles);

When this function is called? Is it called simultaneously with: printf(“Take one down, pass it around, %d bottles of bear on the wall.n”, oneFewer);
or just when this one is finished?

When the numberOfBottles get to 0 the message that will appear is this one: printf(“There are simply no more bottles of beer on the wall.\n”);
And after that, what will happen?


#13

I’ve been pondering this this evening and think I have it.
The function calls itself before completing - that’s why we end up with multiple frames on-top of each other in the stack (rather than one being discarded in favour of a new one).
When the function finally meets the numberOfBottles==0 test it DOES complete (after printing “There are simply no more bottles of beer on the wall”). It’s frame is discarded and the previous one comes to the top.

Here was the eureka moment - (for me at least):
Then the previous iteration of singTheSong gets going again (the one that had called the final version) but from the point it left itself - the only thing it has left to do is:

and remember the frame that is on the top now will contain the appropriate figures. This iteration then finishes, another frame is discarded and the iteration of singTheSong that called it will in turn complete (with figures from the next frame down which is now on the top) and so on and so on and so on until they have all completed and we return to main().

I’ve only really got this straight in my mind this evening so if it’s wrong apologies and I’d appreciate a pointer.


#14

I believe you’ve nailed it, Calcien.


#15

Calcien got it. If I may offer hopefully a clarification:

At the top stack, numberOfBottles = 0, and the output is “There are simply no more…”. That stack completes and goes to the one underneath, which hadn’t completed yet. With that stack, numberOfBottles = 1, so “Put a bottle in the recycling, 1 empty bottles…” is output. Now that stack is completed and goes to the one underneath, which had not completed yet. That stack, numberOfBottles = 2, so “Put a bottle in the recycling, 2 empty bottles…” is output. And so on and so on until the very bottom stack finally completes.

Graphically, here’s another way of looking at it:

sing(numberofBottles=99)

[color=blue] sing(numberofBottles=98)[/color]
.
.
.
[color=green] sing(numberofBottles=2)[/color]

[color=red] sing(numberofBottles=1)[/color]

[color=red] “There are simply no more bottles of beer on the wall.”[/color]

[color=red] “Put a bottle in the recycling, 1 empty bottles in the bin.”[/color]

[color=green] “Put a bottle in the recycling, 2 empty bottles in the bin.”[/color]
.
.
.
[color=blue] “Put a bottle in the recycling, 98 empty bottles in the bin.”[/color]

“Put a bottle in the recycling, 99 empty bottles in the bin.”

Program ends.

Hope this helps someone!


#16

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.


#17

Have to admit this was what brought me here too!!

All is clear up to the point of recycling… Didn’t get why the multiple printf for the recycling lines took place 4 times.