How Does Recursion Work?

To understand how recursion works, we need to look at the behaviour of the run time stack as we make the function calls.

info

The runtime stack is a structure that keeps track of function calls and local variables as the program runs. When a program begins, the main() function is placed on the run time stack along with all variables local to main(). Each time a function is called, it gets added to the top of the runtime stack along with variables and parameters local to that function. Variables below it become inaccessible. When a function returns, the function along with its local variables are popped off the stack allowing access to its caller and its callers variables.

Suppose we have the following program:

unsigned int factorial(unsigned int n) {
    unsigned int rc = 1 ;           //base case result
    if(n > 1) {                     //if n > 1 we  have the recursive case
        rc = n * factorial(n - 1);  //rc is n * (n - 1)!
    }
    return rc;
}


int main(void){
    unsigned int x = factorial(4);
    return 0;
}

Lets trace what happens to it with respect to the run time stack:

Program begins, main() function is placed on stack along with local variable x.

factorial(4) is called, so we push factorial(4) onto the stack along with local variables n and rc.

n is 4, and thus the if statement in line 3 is true, thus we need to call factorial(3) to complete line 4.

info

Note that in each function call to factorial on stack there is a value for n and rc. Each n and rc are separate variables so changing it in one function call on stack will have no effect on values held in other factorial function calls on stack.

Now, the n is 3 which makes the if statement true. Thus, we make a call to factorial(2).

Once again, the if statement is true, and thus, we need to call factorial(1).

Once we make this call though, our if statment is false. Thus, we return rc popping the stack

Once it is returned we can complete our calculation for rc = 2. This is returned, popping the stack

Once it is returned we can complete our calculation for rc = 6. This is returned, popping the stack

Once it is returned we can complete our calculation for rc = 24. This is returned, popping the stack