Creating a factorial function

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

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.




(1 votes, average: 5.00 out of 5)

Leave a Reply |
Tags: C++, factorial, function, recursion, recursive, summation