Understanding recursion in the beer bottle example

Question

I am practicing recursion in C on my own and I found this example online. However there is one thing I don't understand.

void singSongFor(int numberOfBottles)
{
if (numberOfBottles == 0) {
    printf("There are simply no more bottles of beer on the wall.\n\n");
} 
else {
    printf("%d bottles of beer on the wall. %d bottles of beer.\n",
           numberOfBottles, numberOfBottles);
    int oneFewer = numberOfBottles - 1;
    printf("Take one down, pass it around, %d bottles of beer on the wall.\n\n",
           oneFewer);
    singSongFor(oneFewer); // This function calls itself!

    // Print a message just before the function ends
    printf("Put a bottle in the recycling, %d empty bottles in the bin.\n",
             numberOfBottles);
   }
}    

Then I use a main method as such:

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

And the output is as such:

4 bottles of beer on the wall. 4 bottles of beer. Take one down, pass it around, 3 bottles of beer on the wall.

3 bottles of beer on the wall. 3 bottles of beer. Take one down, pass it around, 2 bottles of beer on the wall.

2 bottles of beer on the wall. 2 bottles of beer. Take one down, pass it around, 1 bottles of beer on the wall.

1 bottles of beer on the wall. 1 bottles of beer. Take one down, pass it around, 0 bottles of beer on the wall.

There are simply no more bottles of beer on the wall.

Put a bottle in the recycling, 1 empty bottles in the bin.

Put a bottle in the recycling, 2 empty bottles in the bin.

Put a bottle in the recycling, 3 empty bottles in the bin.

Put a bottle in the recycling, 4 empty bottles in the bin.

I understand the first part very well until I come to "There are simply no more bottles of beer on the wall. I don't understand afterwards how the variable number of bottles is incremented from 1 till 4.

Answer 1

The smaller bottles of beer (and their corresponding recycling) are in inner functions. Your function tree looks like this:

4 bottles of beer on the wall. 4 bottles of beer. Take one down, pass it around, 3 bottles of beer on the wall.
|   3 bottles of beer on the wall. 3 bottles of beer. Take one down, pass it around, 2 bottles of beer on the wall.
|   |   2 bottles of beer on the wall. 2 bottles of beer. Take one down, pass it around, 1 bottles of beer on the wall.
|   |   |   1 bottles of beer on the wall. 1 bottles of beer. Take one down, pass it around, 0 bottles of beer on the wall.
|   |   |   |   There are simply no more bottles of beer on the wall.
|   |   |   Put a bottle in the recycling, 1 empty bottles in the bin.
|   |   Put a bottle in the recycling, 2 empty bottles in the bin.
|   Put a bottle in the recycling, 3 empty bottles in the bin.
Put a bottle in the recycling, 4 empty bottles in the bin.

Answer 2

Step through what this is function is doing in a debugger and you will see exactly how this recursion works. I'm not being pedantic; I literally cannot think of any better way to illustrate what this is doing than referring to this interactive approach.

Answer 3

Just a simple picture explaines:

Answer 4

Note that the last printf uses the numberOfBottles variable, and that is never modified. So upon returning from printing oneFewer bottles, it will print the recycling text with numberOfBottles. Remember that there is one different incarnation of the local variables per each call to the function.

It can be seen easier if you indent the calls to the functions:

4 bottles of beer on the wall...
  3 bottles of beer on the wall...
    2 bottles of beer on the wall...
      1 bottles of beer on the wall...
        There are simply no more bottles of beer on the wall.
      Put a bottle in the recycling, 1 empty bottles in the bin.
    Put a bottle in the recycling, 2 empty bottles in the bin.
  Put a bottle in the recycling, 3 empty bottles in the bin.
Put a bottle in the recycling, 4 empty bottles in the bin.

Now, each line that begins in the same column is written from the same call of the function. Do you see how the number of bottles and recycling coindice? That's because both use the same variable: numberOfBottles.

Answer 5

The recycling statement runs after the recursive call returns.

Each of the recursion calls will eventually finish and the program will continue on to the recycling statement that follows, each with its own local variable values.

Answer 6

With recursion, you can think of everything before the recursive call as being a forward loop, and everything after the call as being a backward loop. (Tail recursion - calling the function again at the end of the function - is often optimized by the compiler into a simple forward loop.)

The way this works is the arguments for each old function are pushed onto the stack, and popped when it all returns. Remember that a stack is last-in, first-out. So since you start with 4, it pushes 4, then 3, then 2, then 1. When the functions return, the stack starts unwinding, so you see the arguments again in reverse order: 1,2,3,4.

Answer 7

The reason it works in this way is that every call of the singSongFor() where numberOfBottles is more than 1 will in turn recursively call singSongFor() until numberOfBottles is 0. At this point printf("There are simply no more bottles of beer on the wall.\n\n") is reached and that function will finish, passing up to the calling function, which will have had an argument of 1 passed in, which then reaches printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles); and itself completes, returning to singSongFor(2)... and so on until you're back at your original number, 4 in this case.