Program to Find Factorial

Problem Statement

Given a non-negative number as input, find its factorial.

Approach 1: Recursion

We can use Recursion to solve this problem. If we observe, we can calculate factorial using the recursive relation :

N! = N* (N-1)!

N! = 0 or 1 if N<=1

Let's See Its implementation.

Code

#include <iostream>
using namespace std;
 
// function to find factorial of a given number
unsigned long long factorial(unsigned long long int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);


}
 
// Driver code
int main()
{
    unsigned long long num = 5;
    cout << num << " Factorial is " << factorial(num) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

5 Factorial is 120

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity: O(N)

We are recursively calling over the whole number until 0.

Space Complexity: O(N)

Recursive stack of O(N)

Approach 2: Iterative

Since recursion can be costly for large numbers, we can also use simple iteration and for/while loops to solve this problem.

Let's See Its implementation.

Code

#include <iostream>
using namespace std;
 
// function to find factorial of a given number
unsigned long long factorial(unsigned long long int n)
{
    unsigned long long ans = 1, i;
    for (i = 2; i <= n; i++)
        ans *= i;
    return ans;
}
 
// Driver code
int main()
{
    unsigned long long num = 5;
    cout << num << " Factorial is " << factorial(num) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

5 Factorial is 120

Complexity Analysis

Time Complexity: O(N)

We are recursively calling over the whole number until 0.

Space Complexity: O(1)

No extra space is required.

Try and compile with online c++ compiler.

FAQs

1. What is the factorial of a number?
   Factorial of a number(non-negative) is the multiplication of all the positive numbers less or equal to the current number. It is denoted by the “ ! ” symbol.
   For example, 5! Or 5 factorial= 5 x 4 x 3 x 2 x 1 = 120.
    
2. Why space complexity in the Recursive approach is O(N)?
   Space complexity in the recursive approach is O(N) because for every number, we call a recursive function fun(N-1), and this goes on until N becomes either 0 or 1. Thereforetack, it is O(N) space due to recursive stackspace.
    
3. What 0 factorial?
   0 factorial or 0! is 1.

Key Takeaways

In this article, we have learned how to find the factorial of a number in C++. We have briefly introduced the topic. We also have given a brief idea of our problem statement of how we will approach this problem. We also explained it is working and how it will go through step by step.

Also read -  Decimal to Binary c++

Recommended Problems:

• Multiplication Recursive
• Multiplication Tree
• Largest BST In Binary Tree
   

We hope this blog might have helped you enhance your knowledge of the factorial of a number. If you wish to practice questions based on Dynamic Programming, you can visit Top Dynamic Programming Questions. If you want to learn about recursion visit Recursion. If you enjoyed reading this article, please give it a thumbs up, which might help me and other ninjas grow. "Happy Coding!".