Understanding Recursion

Recursion is a method where the solution to the problem depends on solution to smaller instances of the same problem.

The most common example for recursion is factorial. Let us see this with an example.

#include <stdio.h>

int factorial(int n){
    int F;
    printf("I am calculating the factorial of %d: ",n);
    if(n==0)
        return 1;
   
    F = n*factorial(n-1);
    printf("The calculation of factorial is done for %d\n",F);
    return F;
}

int main(){
  int n,result;

  printf("Enter the number to calculate the factorial \n");
  scanf("%d",&n);

  result = factorial(n);
  printf("The factorial is %d \n",result);
}

Can you guess what will be the output of this program, how the print statements are printed ?

Let's assume the number for which the factorial is to be calculated is 5.

factorial function is called with value 5--> the first printf statement is printed-->.The recursive function is then called with the value 5.

The calculation of 5*factorial(4) is paused as it needs to calculate the factorial first ie factorial(4).

So, it goes to beginning of function and the second printf statement is then printed -->factorial is called again with value 4,

The calculation 4*factorial(3) is paused as factorial(3) needs to be calculated first.

So, it goes to beginning of function and the third printf statement is then printed -->factorial is called again with value 3,

The calculation 3*factorial(2) is paused as factorial(2) needs to be calculated first.

So, it goes to beginning of function and the fourth printf statement is then printed -->factorial is called again with value 2,

The calculation 2*factorial(1) is paused as factorial(1) needs to be calculated first.

So, it goes to beginning of function and the fifth printf statement is then printed -->factorial is called again with value 1,

The calculation 1*factorial(0) is paused as factorial(0) needs to be calculated first.

So, it goes to beginning of function and the sixth printf statement is then printed. At this point n=0 and the value 1 is returned to factorial(0).

Now the paused calculations take place as follows:

Since factorial(0) =1,
The fifth calculation:factorial(1) = 1*factorial(0) =1 and the print statement is printed with n=1
The fourth calculation:factorial(2) = 2* factorial(1)=2 and the print statement is printed with n=2
The third calculation:factorial(3) = 3*factorial(2) =6 and the print statement is printed with n=3
The second calculation:factorial(4) = 4*factorial(3) = 24 and the print statement is printed with n=4
The first calculation:factorial(5) = 5*factorial(4) =120 and the print statement is printed with n=5

Finally F =120 and the value is printed.

The final output looks like this:

Enter the number to calculate the factorial: 5
I am calculating the factorial of 5
I am calculating the factorial of 4
I am calculating the factorial of 3
I am calculating the factorial of 2
I am calculating the factorial of 1
I am calculating the factorial of 0
The calculation of factorial is done for 1
The calculation of factorial is done for 2
The calculation of factorial is done for 3
The calculation of factorial is done for 4
The calculation of factorial is done for 5
The factorial is 120