C++ Recursion – Factorial

Compiled and Debugged by: Diego 26. Jan, 2010 View Comments

Creating a factorial function

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

C++ Recursion
C++ Recursion – Summation

Example:

factorial(5);

Result:

Iterative version of a function that calculates the factorial

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

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.

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.

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.

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.