INTRODUCTION
This tutorial will guide you on how to write a c++ program to calculate factorial using recursion. Before we write the program I want us to first understand factorial and recursion. Factorial is an important concept in mathematics it is used to find how many ways a number can be arranged. Factorial function was discovered by a mathematician called Daniel Bernoulli in 1726. The concept is used in many mathematical concepts such as permutations and combinations, probability, sequences and series, etc. In a simple term, a factorial is a function that multiplies a number by every number below it till 1. Example, the factorial of 5 represents the multiplication of numbers 5,4, 3, 2, 1, i.e. 5! = 5x 4x 3 × 2 × 1 and is equal to 120. On the other hand, recursion means a function calling itself to solve a smaller part of the problem until it reaches a point where it needs to stop called base case. In this tutorial, you will learn how to calculate factorial in C++ using recursion.
CODE SAMPLE
#include <iostream>
using namespace std;
int factorial(int number){
if(number==0 || number==1){ // base case
return 1;
}else{ //Recursion
return number * factorial(number-1);
}
}
int main(){
int num;
cout << "Please Enter a None-Negative Number to Find it Factorial: ";
cin >> num;
if(num < 0){
cout << "Negative number not allow. Try again with a positive number";
}else{
cout << "The factorial of " << num <<" is " << factorial(num);
}
}
EXPLANATION
Line 3: Creates a function of type int called factorial with 1 argument number of type int
Line 4: Is an if statement that checks if the value of number is 0 or 1. If it is the then program returns 1. This part of the code is called the base case. It is the point that stop the function from calling it self after which the result are propagated back up the call stack.
Line 5: If the value of number is greater than 1 then the function called itself, reduce the value of number by 1 and multiply it by the value of number then return the value. This will be explained in more details later because it is the core part of the program and you need to understand it very well.
Line 10: Is the main function. It is the entry point of the program.
Line 11: Declare a variable num. The variable will store the user input and pass the value to the factorial function when the function is called.
Line 12: Prompt the user to enter a number none negative number
Line 13: Allows the user to enter the number he wants to find it factorial
Line 14: Checks if the number entered by the is not a negative number (Numbers less than 0 are negative numbers).
Line15: Display a message telling the user he entered a negative number.
Line 16: When the number entered is not less than 0
Line 17: Pass the value inputted by the user to the function, Calls the factorial function and display the result to the user.
HOW THE RECUSIVE FUNCTION WORKS
Assuming the user want to calculate the factorial of the number 5. The user enter the value 5 when prompted and when the function is invoked on Line 17 flow of the program is returned back to Line 3 and since the number entered is greater than 0 and 1 the recursive part of the code is executed like below:
1. factorial(5) = 5 * factorial(4)
2. factorial(4) = 4 * factorial(3)
3. factorial(3) = 3 * factorial(2)
4. factorial(2) = 2 * factorial(1)
5. factorial(1) = 1 (base case, return 1)
6. The results are propagated back up the call stack:
a. factorial(2) = 2 * 1 = 2
b. factorial(3) = 3 * 2 = 6
c. factorial(4) = 4 * 6 = 24
d. factorial(5) = 5 * 24 = 120
So the final result is 120.
NOTE: The program does not need a loop. The recursive concept keep on executing the code until the base case is reached and the recursion stops.
TRY IT YOURSELF
Re-write the program to use recursive function but this time use a static value 10. Meaning, your modified code shouldn't prompt the user to enter a number but just pass the value 10 to the function directly.
CONCLUSION
The tutorial teach the reader how to calculate the factorial of a number in c++ using recursion. The tutorial has a source code with a well written step by step guide with explanation on every single line of code and how recursion works.
