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
  3. Example:

    factorial(5);

    Result:

    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.

    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.


    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.


    Related Posts

1 Star2 Stars (1 votes, average: 5.00 out of 5)

No comments yet... Be the first to leave a reply!

blog comments powered by Disqus