Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
The Problem Statement
1.2.
Constraints: 
2.
Solution Approach
2.1.
Brute force Approach
2.2.
Recursive Approach
2.3.
Algorithm
2.4.
Program
2.4.1.
Input
2.4.2.
Output
2.5.
Time Complexity
2.6.
Space Complexity
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Program to Find Factorial of a Large Number Recursively

Author Ujjawal Gupta
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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

  1. 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 :
    1. If ‘N’ <= 1:
      1. If the size of ‘VEC’ is 0:
        1. ‘VEC.PUSH_BACK(N)’.
      2. Return.
    2. Declare ‘CARRY’ = 0.
    3. Iterate ‘i’ from 0 to ‘VEC.SIZE()’:
      1. Update the value of the ‘i’th digit.
      2. Update the value of ‘CARRY’.
    4. While ‘CARRY’ != 0:
      1. Append the remainder after dividing ‘CARRY’ with 10 in ‘VEC’.
      2. ‘CARRY’ = ’CARRY’ / 10.
    5. Call recursion(‘VEC’, ’N-1’).
       
  2. Create the function printArray() that takes ‘VEC’ as a parameter and prints all the elements in ‘VEC’ in reverse order.
     
  3. Create ‘VEC’ and initially assign ‘N’ to it.
     
  4. Call recursion(‘VEC’, ’N - 1’).
     
  5. 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

92

Output

12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000

Time 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. Backtracking vs. Recursion: What's the Difference?
    Recursion: The term "recursion" refers to calling the same function repeatedly and repeatedly. The factorial is a typical example of a recursive function. You'll always require a condition to end recursion (base case).
    Backtracking: Backtracking occurs when an algorithm makes an opportunistic decision* that turns out to be incorrect. The backtracking process would return the system to its previous state if the decision were wrong. It selects candidates for the solution and discards those who fail to meet the requirements. The Eight Queens Puzzle is an excellent example of a problem to solve. In Neuronal Networks, backtracking is also often utilized. Backtracking is frequently not done recursively. Backtracking that employs recursion is referred to as Recursive Backtracking.
  2. What distinguishes Dynamic Programming from Recursion and Memoization?
    Memorization is the process of storing past function call outcomes (a real function always returns the same thing, given the same inputs). Before the findings are stored, it makes no difference in terms of algorithmic complexity.
    The approach of a function calling itself, usually with a reduced dataset, is known as recursion. This has little bearing on algorithmic complexity because most recursive functions can be transformed to similar iterative functions.
    The method of answering easier-to-solve sub-problems and building up the answer from there is known as dynamic programming. Most DP algorithms will be somewhere between a Greedy (if one exists) and an exponential (enumerate all options and choose the best one) approach in terms of execution time.
    Recursion can be used to implement DP algorithms, but it isn't required. Memoization cannot speed up DP algorithms since each sub-problem is only solved (or the "solve" function is only called) once.
  3. In recursion, the condition for which the function will stop calling itself?
    For recursion to end at some point, there always has to be a condition for which the function will not call itself. This condition is known as base case.
  4. In recursion, define memory allocation for different function calls.
    When a function is invoked, memory on the stack is allocated to it. It's also possible to say that for that function, an activation record is created, which is a data structure that stores values connected to the function, such as:
    The callee function's local variable
    The caller function's return address is used so that once the function is executed, it is possible to determine which function is responsible for the value returned by the callee function.
    If there is one, the callee function's parameter. An activation record is stored on the memory stack when a function is called. The record is deleted from the memory stack when this function is fully performed, thus freeing up memory.
  5. What is the Recursion Tree Method?
    Each node of the recursion tree indicates the cost of specific recursive subproblems in the recursion tree approach. To determine the algorithm's complexity, we add each node's values together.
    The steps for using the recursion tree approach to solve a recurrence relation are as follows:
    Create a recursion tree using the recurrence relation provided.
    Decide how many levels there will be and how much each one will cost.
    Finally, simplify the relationship by adding the cost of each level.

Conclusion

We have learned the problem of how to find the factorial of a large number recursively. We have seen that the time complexity is O(N), and it takes O(K) extra space.

If you want to explore more, then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. 

Recommended Problems:

Till then, Happy Coding!

Previous article
Fibonacci Using Recursion
Next article
Count All Positive Integers Having N digits and the absolute difference between any two adjacent digits is K.
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass