Questions about 99 Beers/recursion program


#1

When the program gets to [color=#00BFFF]singTheSong(oneFewer);[/color] that takes it back up a few lines to [color=#00BFFF]int oneFewer = numberOfBottles - 1;[/color] correct? And it keeps going in a loop subtracting a bottle each time? Then how does it know to go back to the top to print there are no more bottles? Why wouldn’t it just keep subtracting? Also, after it prints that there are no more bottles, why doesn’t it just stop there? I thought that the if/else thing would stop the program at the if when it met the requirement.

Also, what is making the program add the numbers upward for the recycling bin? I see only the subtraction part [color=#00BFFF](int oneFewer = numberOfBottles - 1;)[/color]. Is it the [color=#00BFFF]singTheSong(oneFewer);[/color] part that triggers the recycling bin adding up part? I don’t understand what happens after the [color=#00BFFF]singTheSong(oneFewer);[/color] part, can someone explain that to me?


#2

I am gathering information to help you…

Are you comfortable with the concept of recursion in mathematics?

Specifically, are you comfortable with these recursive definitions:

10! = 9! * 10
10! = 8! * 9 * 10
10! = 7! * 8 * 9 * 10
...
With 0! = 1

or
Factorial (10) = Factorial (9) * 10
Factorial (10) = Factorial (8) * 9 * 10
Factorial (10) = Factorial (7) * 8 * 9 * 10
...
With Factorial (0) = 1

or 
Factorial (N) = Factorial (N - 1) * N
with Factorial (0) = 1

#3

I know nothing about recursion in mathematics. The first line says to me that 10 does not equal 9x10, which I’m sure is a completely wrong translation of that equation.

Am I correct in assuming that coding in C is a lot like algebra? In school I did well in algebra, but this stuff escapes me.


#4

If you did well in Algebra, than fear not :slight_smile:

First, recursion in mathematics.

10! = 9! * 10
Actually, you are quite wright; the above expression looks like this:
10 != 9! * 10
Which in C means 10 is not equal to 9 …

But when I wrote it down, I was not thinking about any programming at all; I wrote is as a mathematical equality:
10! = 9! * 10
Which means factorial of 10 equals factorial of 9 times 10.

From this we can generalize:
N! = (N-1)! * N with 0! = 0 (factorial of zero is defined as 1)

This is easy to verify:
For N = 10
10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
9! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9
8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8

1! = 0! * 1

Since factorial of zero is defined as one, we stop at zero:
0! = 1

Therefore:
10! = 9! * 10

But we can’t write 10! in C programs to mean the factorial of ten as you have discovered, because the grammar of the C language does not allow us.

But we can write factorial (10), Factorial (10), fac (10), Fac (10), … instead:

Therefore:
Factorial (10) = Factorial (9) * 10
Factorial (9) = Factorial (8) * 9

Factorial (1) = Factorial (0) * 1
Factorial (0) = 1

Now we can go one step further and generalize:
Factorial (N) = Factorial (N-1) * N

As long as we stick to the definition that Factorial (0) equals 1.

If you look closely, you will see that the above definition is using itself on the right hand side; this is called recursion.

Here is another example:
GNU = GNU is not Unix

If this does make sense, try writing a program that computes the factorial of a natural number (an integer).
To stop the recursion, use the rule: Factorial (0) equals 1.

Also, if you can, read this book: "The C Programming Language, Brian W. Kernighan and Dennis M. Ritchie."
if you want to be a good programmer.


#5

I don’t have any idea what ibex is on about, but your problem starts here…

Not correct. You ‘jump back’ to the start of the entire function again.

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

This means that the number of bottles is reevaluated in the ‘if’ statement, allowing the loop to stop if that number is zero (because it never reaches the ‘else’ and therefore doesn’t call itself again.

Hopefully that’s more like the answer you were expecting.


#6

It is all about teaching a man how to fish on its own :slight_smile:


#7

[quote=“ibex10”][quote]
I don’t have any idea what ibex is on about, but your problem starts here…
[/quote]
It is all about teaching a man how to fish on its own :slight_smile:[/quote]

No, he asked if his hook was tied on correctly, and you gave him a lecture on the breaking strain of various types of line depending on its synthetic composition and the ambient temperature. When you left, he still didn’t know if his hook was tied on correctly.


#8

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.


#9

I’ve really struggled with the 99 beers recursion issue (mostly following the flow and figuring out how the compiler is reading/understanding the various arguments and functions. The answers on theses boards have helped tremendously and I get the stack and the recursion, HOWEVER, there is one thing that has me stumped.

Once the number of bottles hits zero it triggers the “if” statement, skipping the else, yet the:

line is still triggered even though it appears to be nested within the “else” clause (or is it an argument?).

I could understand it if the printf line was preceded by a “}” closing out the scope of the “else” clause (and it still works this way) but it isn’t.

???


#10

That’s because when the if-else statement executes, with numberOfBottles == 0, the control returns to the point immediately after the line that (recursively) invoked the singTheSong (int) function, and that point happens to be inside the else part of the if-else statement.

If it still doesn’t make sense, don’t worry about it too much at this stage. You can rewrite any program that uses recursion as one that doesn’t use recursion.

The example in the book is cluttered with the print statements, making it harder for you to see how the recursion works. Try writing a function that recursively adds all the numbers from 0 to N, where N can be any number greater than or equal to 0. Also write the same function without recursion.


#11

Like others, I was specifically confused about why the code was ending by printing out the last printf increasing from 1-99…

I understood recursion and the stack/frames, but I was stumped on this nagging point because I couldn’t see where the value of numberOfBottles was getting incremented or decremented, or set to 1, or any other sort of numerology related to that variable other than the fact that it is being used by the formula that sets the value of oneFewer.

Then I realized that each time singTheSong() is called it is passing the value of the oneFewer variable as the argument into singTheSong (int numberOfBottles) which is where the value of the variable numberOfBottles is being updated for each frame and hence the incrementing printf statement that starts with 1, because 1 is the value of numberOfBottles in the top frame on the stack as it gets emptied.

Bill


#12

Thanks Bill, that did it for me.
:stuck_out_tongue:


#13

i had the exact same question about the adding up of the bottles in the recycle part of the execution.

from what i have read here, it seems that the line that says printf("put a bottle in the recycling bin…etc.
is postponed every time the singTheSong(oneFewer); function is called.

once the number of bottles gets to zero and the function call is skipped , it goes back to finish all the last lines that were passed over one by one starting at the top of the stack.

I copied this last line and added it above the function call and it counted down with each recursion then up at the end.

This is a tough pill to swallow but I think we need to take what happened and internalize it. maybe it will give us insight in the future when we need it.

Hey, I went back and added this below the last printf statement about recycling.

int timesthru=0;
timesthru++;
printf(“this is the %dth time through this part.\n”,timesthru);

when it ran, it said " this is the 1th time through this part. " every single time. i guess it got reset to zero each time it was executed.
then i put the declaration at the very beginning of the program to keep it from being set to zero and it counted up 1,2,3,4,5
then I moved the increment (timesthru++;) above the singTheSong(oneFewer); line and it printed 5th time though every time .because it incremented on each loop
(I didn’t use 99 bottles …only 5. I’m not much of a drinker).

I don’t know what my point is. but if you add some lines like this it will give you some idea of what happens when and what repeats an what doesn’t.


#14

Shouldn’t there be a right bracket – } – immediately after the line of code:

singTheSong (oneFewer);

replacing the right bracket appearing immediately after the next line:

printf ("Put a bottle in the recycling … // etc. etc.


#15

[quote=“potato23”]Shouldn’t there be a right bracket – } – immediately after the line of code:

singTheSong (oneFewer);

replacing the right bracket appearing immediately after the next line:

printf ("Put a bottle in the recycling … // etc. etc.[/quote]

I’m going to follow this post with a post I wrote in the General Book Discussion section of this forum on the same topic. It is my belief that the “Bottles of Beer” recursion program has errors.

I think that your observations are precise and accurate.The program in the book on page 34 is a mess.

When the variable numberOfBottles reaches zero, the very first printf statement in the function (the if part of the if/else condition) will finally execute, generating the following output: There are simply no more bottles of beer on the wall. Up to this point, the program works fine and logically. But not beyond this point.

To get the rest of the output as shown on page 35 – the sequence of 99 separate “recycling” lines that increment the # of bottles from 1-99, one bottle per line, you’ll have to write more code. This program leaves you hanging. As it’s written, the “recycling” line is programmed to execute in the else part of the if/else condition. But this is illogical --a programming error in logic – because once the variable numberOfBottles reaches zero, the if portion of if/else executes and the else portion is skipped, never to execute again.

But even if that printf line about the recycling bin were to execute, there is no code to increment the # of bottles by one in the “recycling” line. And the output generated by that last printf statement wouldn’t match the output on page 35 of the text. With the variable numberOfBottles still set to 0, the output would be: Put a bottle in the recycling, 0 empty bottles in the bin. This is also wrong, because the output on page 35 shows that the first recycling line includes 1 empty bottles in the bin, not 0.

You could write a loop to correct the rest of program, but loops aren’t introduced for two more chapters. So if not a loop, then perhaps another recursive function to generate the “recycling bins” lines.

Here’s how I’d fix the rest of the program, there are several options:

First, I’d delete the last printf statement from the singTheSong() function.

Then, my new main:
{
singTheSong(99);
singTheSecondVerse(1);
return 0;
}

And finally, the new singTheSecondVerse() function, which is recursive, in keeping with the lesson theme:

void singTheSecondVerse(int numberOfBottles)
{
if numberOfBottles < 100 {
printf(“Put a bottle in the recycling, %d empty bottles in the bin.\n”, numberOfBottles);
numberOfBottles += 1;
singTheSecondVerse(numberOfBottles);

}

}


#16

Maybe I don’t understand your problem correctly, but my code, copied from the book, worked exactly as promised: counting down, untill and with “no more beers…”, then counting up.


#17

Yeah, I figured it out last night. I discovered that this was covered extensively in some other threads, where many posters raised the exact same issue. Those threads answered my questions, or rather, corrected my incorrect assumptions.

My problem is that I haven’t installed XCode, Cocoa etc. and so for now, I’m working through the book by simply reading the code, but not running the programs or experimenting in the computer to enhance the lessons. And the code itself doesn’t hint that the else condition would continue to execute, even when the if condition is met.

I now understand how the bottle of beer program works, but I still struggle with the concept because, once the frames on the top of the stack are in the process of being discarded (“popped off”), why should they continue to execute? I would think, Intuitively, that the frame executes when it is first placed on top of the stack, and then that frame is done – finished. I would expect that frames in the process of being discarded, or popped off the top of the stack, simply get thrown away. They’re done with, I would think. Yet they continue to execute. It’s strange.

Yet on the other hand, you could argue that if the frame is done with after it’s first placed on top of the stack and executed, why isn’t it discarded immediately. I guess that the frame remains because it may execute again. Does this concept only apply to functions that call themselves? In other words, if there is additional code in the recursive function, following the line of code that has the function call itself, are those additional lines of code always the lines that get executed by frames popping off the stack?

Thanks for your response.


#18

I am sure you have good reason to read the book instead of typing it in. But I can tell you my experience: By typing in the code, and at times insert extra log messages and working with the code hands-on, I couldn’t have learned as much by only reading the book.
Good luck, anyway!


#19

Your explanation helped a lot.


#20

It took me about an hour of thinking about this to finally understand it. The replies here helped somewhat, but not totally, so I just wanted to post my interpretation.

There are 5 stacks of singSongFor(). Think of these as 5 different scopes and values for the same function. 5 cards on top of eachother. When we first call singSongFor(), we pass along the value 4 in the main() function. singSongFor(4) Here are the values on the stacks as follows

FIRST STACK

singSongFor(4)
numberOfBottles = 4 // this value was passed from main()
oneFewer = 3
singSongFor(oneFewer) //we pass 3 the second time

SECOND STACK

singSongFor(3)
numberOfBottles = 3 // this value was passed from the first stack of singSongFor()
oneFewer = 2
singSongFor(oneFewer) // we pass 2 the third time

THIRD STACK

singSongFor(2)
numberOfBottles = 2 // passed from the second stack of singSongFor()
oneFewer = 1
singSongFor(oneFewer) // we pass 1 the fourth time

FOURTH STACK

singSongFor(1)
numberOfBottles = 1 //passed from the third stack of singSongFor()
oneFewer = 0
singSongFor(oneFewer) // we pass 0 the 5th time

FIFTH STACK

singSongFor(0)
numberOfBottles = 0 // passed from the fourth stack.

Because of our if/else condition, we print the statement “There are no more bottles of beer on the wall” and the function ends. Or rather this stack is discarded, and we must return to the function that called this function and resume that functions execution. In other words, stack 4 called stack 5. Stack 5 is done, so we go back to the printf() statement in stack 4 that says printf(“Put a bottle in recycling, %d bottles in recycling\n\n”, numberOfBottles) // numberOfBottles was 1 here (see above) so we print that. Stack 4 is done! we go to stack 3, back to that same statement following the function call. We print numberOfBottles as 2 here because that’s it’s value on that stack. Stack 3 is done! Revert to stack 2 and we simply repeat this until all of the singSongFor() stacks are complete. We then similarly go back to the statement immediately following the function call of stack 1, which was in main(). The statement following the function call was return 0; and thus the program ends execution.

Hoped this helped someone a tiny bit at least. It helped me to think about it very visually.