Introduction
Recently, Ninja has taken admission to college. His maths teacher wants to check his maths of Ninja, so he gives a number ‘N’ to Ninja and asks him to find the factorial of that number. Ninja is very weak in mathematics, so he wants a program in which if he enters any number, it returns the factorial of that number. Your task is to help Ninja by writing that program.
The above problem is the standard recursion problem. Recursion based-coding problems are widely asked in various coding contests and various coding interviews.
In this blog, we will solve the above problem using recursion.
The Problem Statement
You are given an integer ‘N ’. Your task is to find the factorial of ‘N’. Factorial of any number ‘N’ is the product of ‘N ’, ‘N - 1’, ‘N - 2’, . . . ,2,1.
Constraints:
1<= N <=100
Example
Let N = 5, then factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120.
Hence, the factorial of 5 is 120.
Solution Approach
Brute force Approach
The naive approach of the above approach is to multiply all the numbers between 1 to ‘N’.
But the range of long int is around 10^18, so the variable cannot store the value greater than the range of long int. Hence, the brute force approach is inefficient for N>18.
Recursive Approach
It is the most efficient approach to finding the factorial of any number. We store the value of each digit of the resulting number in the array.
The algorithm is as follows:
Algorithm
-
Define the function recursion(), which takes ‘VEC’ and ‘N’ parameter arrays. Here, ‘VEC’ stores the multiplication of all the numbers from ‘N’ to the given number :
-
If ‘N’ <= 1:
-
If the size of ‘VEC’ is 0:
- ‘VEC.PUSH_BACK(N)’.
- Return.
-
If the size of ‘VEC’ is 0:
- Declare ‘CARRY’ = 0.
-
Iterate ‘i’ from 0 to ‘VEC.SIZE()’:
- Update the value of the ‘i’th digit.
- Update the value of ‘CARRY’.
-
While ‘CARRY’ != 0:
- Append the remainder after dividing ‘CARRY’ with 10 in ‘VEC’.
- ‘CARRY’ = ’CARRY’ / 10.
-
Call recursion(‘VEC’, ’N-1’).
-
If ‘N’ <= 1:
-
Create the function printArray() that takes ‘VEC’ as a parameter and prints all the elements in ‘VEC’ in reverse order.
-
Create ‘VEC’ and initially assign ‘N’ to it.
-
Call recursion(‘VEC’, ’N - 1’).
- Call printArray(‘VEC’).
Program
#include <iostream>
#include <vector>
using namespace std;
// Define recursive function.
void recursion(vector<int> &vec, int n)
{
// Base condition to terminate the recursive call.
if (n <= 1){
if(vec.size()==0) vec.push_back(n);
return ;
}
// To store the carry after dividing with 10.
int carry = 0;
for (int i = 0; i < vec.size(); i++)
{
// Update value of ith digit.
vec[i] = (vec[i] * n + carry);
// Update carry
carry = vec[i] / 10;
vec[i] = vec[i] % 10;
}
// Inserting remaining digits.
while (carry)
{
int rem = carry % 10;
vec.push_back(rem);
carry /= 10;
}
// Call recursive function.
recursion(vec, n - 1);
}
// Function to print the vector.
void printArray(vector<int> &vec)
{
int s = vec.size();
for (int i = s - 1; i >= 0; i--)
{
cout << vec[i];
}
}
int main()
{
// Taking 'N' as an input.
int n;
cin >> n;
// Creating vector which initially store the value of 'N'.
vector<int> vec;
int temp = n;
while (temp != 0)
{
int rem = temp % 10;
vec.push_back(rem);
temp /= 10;
}
// Call recursion().
recursion(vec, n - 1);
// Call printArray.
printArray(vec);
return 0;
}Input
92Output
12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000Time Complexity
O(N), where ‘N’ is the given number.
As there are total ‘N’ recursive calls in the program.
Space Complexity
If ‘K’ is the total number of digits in the answer then O(K).
As we are storing the answer in the vector, the vector's size is dependent on the number of digits in the solution.
Must Read Recursion in Data Structure
305+ registered