C++ Recursion – Factorial

Creating a factorial function

Below is an example of how to calculate the factorial of n. This tutorial expects you to understand the following:

  1. C++ Recursion
  2. C++ Recursion – Summation

Example:

1

factorial(5);

Result:

1

120

Iterative version of a function that calculates the factorial

To understand how to calculate the factorial using recursion, let’s write a simple algorithm that will do it for us using iteration.

1
2
3
4
5
6
7
8
9
10
11

int factorial(int n) {
 
     //Initial value for the final value is 1
     int factorial = 1;
 
     for ( int i = 2; i <= n; i++ ) { 
          factorial = factorial * n;
     }
 
     return factorial;
}

Calculating factorial using recursion

So how would we go by solving this using recursion? First of all we need a function header.


1

int factorial(int n)


Next, what would be our base case? When we are trying to calculate the factorial for 0, the result should be 1. 


1
2
3
4
5

int factorial(int n) {
 
     //Return 1 when n is 0
     if ( n == 0 ) return 1;
}


Now, how would we go on by computing the factorial using recursion? Let’s come up with a formula by calculating the factorial of 2,3, and 4.

1
2
3
4
5
6
7
8
9
10
11

factorial(1) = 1;
 
factorial(2) = 2 * factorial (1) = 2 * 1 = 2;
 
factorial(3) = 3 * factorial (2) = 3 * 2 = 6;
 
factorial(4) = 4 * factorial (3) = 4 * 6 = 24; 
 
...
 
factorial(n) = n * factorial(n-1);



Translating the above formula to code, is then fairly trivial. This would allow us to apply our factorial formula to any positive integer.

1
2
3
4
5
6
7
8

int factorial(int n) {
 
     //Return 1 when n is 0
     if ( n == 0 ) return 1;
 
     //factorial(n) = n * factorial(n-1);
     return n * factorial(n-1);
}


Have any questions? Feel free to ask below or request any other examples.

Tags: , , , , ,