macOS Can someone please explain this recursion example to me?

[chrono1081]

Hi guys,

A friend of mine asked me to explain a recursion example to him in the Big Nerd Ranch Objective-C book, however it has me stumped too so I can't really explain it.

The code below is the example and I commented the line that confuses me:

#include <stdio.h>
#include <stdlib.h>

void singTheSong(int numberOfBottles)
{
if(numberOfBottles == 0)
{
printf("There are no more bottles of beer.\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", oneFewer);

singTheSong(oneFewer);

printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles); //This is the confusing line
}
}

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

return 0;
}

The output of the program looks like this:

...
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 no more bottles of beer.
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.
...

I don't get how the line about putting the empty bottles in the bin is called repeatedly.

Although I own the book I don't have it to look at (my friend borrowed it) so I'm not sure if the book explains it or not. I am confused at how the "Put a bottle in the recycling, n empty bottles in the bin" can get called over and over. I assume it has something to do with being popped off the stack but I'm really at a loss for how to explain this.

 

[balamw]

I don't get how the line about putting the empty bottles in the bin is called repeatedly.

I had a quick peek it's dealt with in terms of the stack.

The first bottle is taken down passed around and then kept on the stack to put away in the recycling bin. So the first call handles the first bottle down and the last bottle in the bin.

B

 

[chrono1081]

I had a quick peek it's dealt with in terms of the stack.

The first bottle is taken down passed around and then kept on the stack to put away in the recycling bin. So the first call handles the first bottle down and the last bottle in the bin.

B

Oh geez, ok I see what its doing.

Basically on the way down to 0 bottles on the wall the singTheSong() never fully finishes execution. It can never get to the last line which is:

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

Once the numberOfBottles == 0, then everything on the stack finishes executing that last statement.

Bah. I'm too tired to think like this at the moment. I'm off to bed

Thank you for the help!