Finding Factorial of a Number using Recursion

Factorial of a Number

We know how to find the factorial of a number. We learned this in High school, didn’t we? Let’s revise it once again. 

Factorial of a non-negative integer n is the product of all integers less than or equal to n.

n! = n * (n-1) * (n-2) * … * 3 * 2 * 1

Or

n! = n * (n-1)!

Example: 5! = 5 * 4 * 3 * 2 * 1 = 120

This problem can be solved recursively. For this, we first need to write the base case and then the recursive case.

The Base Case

Think about the smallest problem. It is factorial of 1, and we already wrote the code for the base case. It is

if (n == 1) {  //If factorial of 1 needs to be found
    return 1;   // then return 1 as the result. 
}

The Recursive Case

If you observe the formula i.e. n! = n * (n-1)! carefully, the problem of finding n! can be solved if we know the values of n and (n-1)!. This is the essence of recursion. The factorial of n is easy to find if we know what is the factorial of n-1. So, the big problem (which is factorial of n) can be solved by finding factorial of n-1 (which is the smaller version of the same problem). And, writing the recursive case is pretty straightforward. Following is the recursive case of factorial of n (assuming the fact(n) represents factorial of n):

return n * fact(n-1);

That’s it 😀. Easy right?

Now, the complete factorial function is as follows:

int fact(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    // Recursive case
    else {
        return n * fact(n-1);
    }
}

The above program is capable of finding the factorial of any positive integer.

You may have this question in mind, how the program is capable of returning factorial of n. How does it know the value of factorial of n-1? To understand this, we need to uncover the mystery of what goes behind the scenes when a function is called. Let’s understand the complete process.

Behind the Scenes

Let’s say the function fact(n) is called from the main() function. The complete program looks like the following:

#include <stdio.h>

int fact(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    // Recursive case
    else {
        return n * fact(n-1);
    }
}

int main() {
    printf("%d", fact(3));
    return 0;
}

Whenever a function is called, its activation record is created inside the call stack.

First, the main() function is called, so the activation record of the main() function goes inside the call stack as shown in the following figure:

Next, fact(3) is called with n = 3. This means the factorial of 3 needs to be calculated. Therefore, the activation record of fact(3) with the local variable n = 3 is added in the call stack as shown below:

From the above figure, you can observe that the activation record of fact(3) is placed above the activation record of main(). As there is only one entry point, which is the top of the stack, the activation records are always placed on top of the other, and it is not meaningless. The top of the stack indicates the current function under execution. As currently, the top of the stack (the activation record placed at the top) belongs to fact(3), therefore it tells us and the computer that fact(3) is under execution; not main(). When fact(3) completes its execution, its activation record will be removed. This simple concept of adding and removing the activation record allows the call stack to keep track of the function calls.

Now, we are within the fact(3) function with n = 3. Let’s get inside the function. It can be observed that the base case is of fact(3) is not satisfied because n is not equal to 1. Therefore, the recursive case (else block) will be executed. The recursive case is as follows:

return n * fact (n-1);

This statement returns the result of n * fact(n-1) which is equal to fact(n). We know the value of n, but we don’t know yet what the value of fact(n-1) is. This means in order to return the result of fact(n), we need to resolve fact(n-1) first. So, the current execution will pause for a moment and the control shifts from fact(n) to fact(n-1). This means fact(n-1) is called, and therefore the activation record of fact(n-1) goes inside the stack as shown below:

It can be observed inside the call stack, the activation record of fact(2) is placed above the activation record of fact(3). This shows that fact(3) has not completed the execution yet, and the control has been transferred to fact(2). So, at this moment, we are within fact(2) with n = 2. Again notice that the base case is not satisfied, therefore the recursive case will execute. According to the recursive case, in order to find fact(2), one has to find fact(1) because fact(2) = 2 * fact(1). So, first fact(1) needs to be resolved, and therefore fact(1) is called. The activation record of fact(1) is added in the call stack. The following figure shows the current situation of the call stack:

Now, fact(1) is under execution with n = 1. As n is 1, the base case is satisfied, and 1 returned from the function to the caller of fact(1). The keyword return literally means “return where we left off”. There are two things happen when we return from a function:

1. We return to the place where we left off last time. 
2. The activation record associated with the returned function is removed from the stack. This means all the local variables of the function are destroyed too.

The local variable of fact(1) is n with value 1. This variable will be destroyed. After returning from fact(1), the current state of the call stack is shown below:

Do you remember where we left off? This can be observed from the call stack. After removing the activation record of fact(1), the new top of the stack is the activation record of fact(2). So, we are now inside fact(2). Simple! 

We know the value of n is 2 in this function, so in the recursive case, n is replaced by 2, and fact(1) is replaced by 1 which is the return value of fact(1). 

return 2 * fact(1)
return 2 * 1
return 2

So, value 2 is returned from fact(2) to the place where we left off. We can say fact(2) has completed execution, and therefore, its activation record will be removed. After removing the activation record of fact(2), the activation record of fact(3) is the new top of the stack. This tells us we are within fact(3). 

The recursive case of fact(3) is as follows:

return n * fact(3);
return 3 * 2;
return 6;

So, value 6 is returned from fact(3) and the activation record of fact(3) is removed. But, where is it returned? As shown below, the new top of stack is main(), so value 6 is returned to main() inside the printf() function.

Because of the printf() function, value 6 is displayed on the screen which is the factorial of 3 🥳

The following video is like the summary of what we have learned so far about the recursive process of factorial of n.

I hope the entire process of what goes behind the scenes of a recursive procedure is completely clear. 

In the next tutorial we will take one more example to further solidify our understanding about recursion.