Confused about recursion in C

Question

I have the following code:

#include <stdio.h>

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);
    }
}

int main(int argc, const char * argv[]) {
  
    // We could sing 99 verses, but 4 is easier to think about
    SingSongFor(4);
    
    return 0;
}

According to my understanding the program must terminate after it prints:

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

But how come it resumes to print:

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.

The if functions already printed out a message, but instead of terminating it gets to the else as well. How is this possible? And How is there a increment from 1 to 4 in "numberOfBottles"?

Update : This is my understanding of the code. Please correct me if I'm wrong.

Answer 1

In your code:

    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);

The call to the SingSongFor function does not return until it has completed (and all the child functions which it called have also completed).

So the printf line is forced to wait until all the lower SingSongFor calls have finished, before it will run.

In other words, calling a function does not queue it up for execution in future, it runs that function immediately, and execution of the current function is paused until the called function has finished.

This process is why function calls create a stack of execution states, with each stack entry holding the local values that will be needed when execution at that level resumes (in this case, just the numberOfBottles variable, and the memory address of the next instruction to that is waiting to run).

This pushing and popping of stack entries can make recursion (briefly) consume a lot of memory, and in the worse case, when the stack fills up too much memory, this can result in ... a stack overflow!

Answer 2

If I understand you only want to print the total in the recycle bin once when the recursion completes, then the easiest solution is to use a wrapper (or helper) function to call SingSonfFor. By using a wrapper, you preserve the original numberOfBottles as the count for the recycle, while each bit of recursion will reduce the number by one. Example:

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

void SingSongFor (int numberOfBottles){

    if (!numberOfBottles)
        return;

    int oneFewer = numberOfBottles - 1;

    printf (" %d bottles of beer on the wall. %d bottles of beer.\n", 
            numberOfBottles, numberOfBottles);

    printf (" Take one down, pass it around, %d bottles of beer on the wall.\n\n", 
            oneFewer);

    if ((oneFewer) == 0)
        printf (" There are simply no more bottles of beer on the wall.\n\n");
    else 
        SingSongFor (oneFewer); // This function calls itself!
}

void ss_helper (int numberOfBottles)
{
    SingSongFor (numberOfBottles);

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

    if (numberOfBottles >= 6)
        printf ("\n Now go sober up you lush...\n\n");
}

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

    // We could sing 99 verses, but 4 is easier to think about
    int coldbeers = (argc > 1) ? atoi (argv[1]) : 4;
    // SingSongFor (coldbeers);
    ss_helper (coldbeers);

    return 0;
}

output:

$ ./bin/beersong
 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, 4 empty bottles in the bin.

Answer 3

The reason it's derpy is because you're calling the next function BEFORE you print the number of bottles in the current function. So when it all catches up, the last function prints first.

Currently:

    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);

What you Want:

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

That way, you'll get the output you expect and THEN the next step-down happens.

Answer 4

To understand why your program acts as it does, it's necessary to understand how a function call works. The fact that it's recursive might enable the compiler to make some optimizations that improve the efficiency of the program, but conceptually being recursive doesn't really change what is happening.

First, let's examine an alternative program that does basically the same thing as your program, using non-recursive function calls.

void SingSongFor4(){

        printf("4 bottles of beer on the wall. 4 bottles of beer.\n");

        printf("Take one down, pass it around, 3 bottles of beer on the wall.\n\n");

        SingSongFor3();

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

void SingSongFor3(){

        printf("3 bottles of beer on the wall. 3 bottles of beer.\n");

        printf("Take one down, pass it around, 2 bottles of beer on the wall.\n\n");

        SingSongFor2();

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

void SingSongFor2(){

        printf("2 bottles of beer on the wall. 2 bottles of beer.\n");

        printf("Take one down, pass it around, 1 bottles of beer on the wall.\n\n");

        SingSongFor1();

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

void SingSongFor1(){

        printf("1 bottles of beer on the wall. 1 bottles of beer.\n");

        printf("Take one down, pass it around, 0 bottles of beer on the wall.\n\n");


        printf("Put a bottle in the recycling, 1 empty bottles in the bin.\n");
    }
}

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

    // We could sing 99 verses, but 4 is easier to think about
    SingSongFor4();

    return 0;
}

I hope that it's obvious that each function prints a couple of lines, calls the next function, then prints another line. Each called function does this in turn so, for example, 2 lines for SingSongFor4() are printed, then SingSongFor3 is called. This prints its 2 lines, then calls SingSongFor2(), which prints its lines and so forth. SingSongFor1() doesn't call any other functions so it prints all three lines then returns to SingSongFor2() which completes and so on up the chain. In all you get the 8 lines of X bottles on the wall/take one down as you follow the function calls "down", then the 4 lines of "Put a bottle in the bin" as you return "up" the reverse direction.

Your function isn't any different except that it's been parameterized and had a little logic added to determine when it should act like SingSongFor1() and when it should act like the other 3. I say it's not different except that in your case you have a single copy of the text of the program that's shared by each invocation of the program rather than 4 separate (nearly identical) copies of the text. What makes it possible to share a copy of the text is the local context of each function call - the parameters, variables, and some housekeeping information about where the program lives and the state of execution of the program.

Typically this context information is contained in a special data structure called the stack. It's called a stack because you stack things one on top of the other, then remove them one at a time from the "top." Each stack frame contains the context of one invocation of the function: the parameters - in your case numberOfBottles; the local variables - oneFewer; and information about which statement should be executed when the function ends or returns. When a function is called the frame corresponding to that call is pushed onto the stack and the text of the function is executed. When it finishes, the frame is popped off and execution resumes in the calling function at the point where it left off (which was stored in the popped off stack frame for this purpose). It resumes using the new "top" frame of the stack for it's context.

The important thing, though, is that your recursive function works exactly the same way as any other function - each time it's called it gets a new context of its very own, even though the text of the function is the same. It executes to completion then returns to the previous context - which may have been the same function, though with a different context.

Answer 5

Everything is just right. When you reach the final message There are simply no more bottles of beer on the wall. your program returns to the point where it was called (it was called in function SingSongFor with argument 1). Then prints the message Put a bottle in the recycling, 1 empty bottles in the bin. and returns to previous call in function SingSongFor with argument 2. And like this up to 4.

Answer 6

The recursive function calls are stacked. So it goes something like this:

SingSongFor(4)
  |
  v
SingSongFor(3)
  |
  v
SingSongFor(2)
  |
  v
SingSongFor(1)
  |
  v
SingSongFor(0)

The last call prints that there are no more bottles and then returns and this is there the magic happens: It returns to the previous call, which will then print the message about the recycling bin, and return to the previous call which again print its message, and so on.

Answer 7

3 bottles:

SingSong(3):
 PRINT 2 LINES
 SingSong(2):
     PRINT 2 LINES
     SingSong(1):
          PRINT 2 LINES
          SingSong(0):
               PRINT 1 LINES
          PRINT RECYCLE LINE
     PRINT RECYCLE LINE
 PRINT RECYCLE LINE

After your final inner recursive call happens, it then backs its way out through each method call and calls the recycling message.

Answer 8

After the line

 SingSongFor(oneFewer); // This function calls itself

You have a printf i.e.

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

So that is what the program does. With the value of numberOfBottles that is stored on the stack.