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

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.