Problem Statement

Calculate the factorial of a given number n.

Examples

Example 1:

Input: 5

Output: 5! = 5 * 4 * 3 * 2 * 1 = 120

Theory

Factorial of non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. Mathematically, it is defined as:

n! = n * (n-1) * (n-2) * ... * 2 * 1

Also, by definition:

0! = 1

Different Approaches

1 Iteration

Iterative approach can also be used to calculate factorial without recursion.

Code Implementation in C++:

#include <iostream>
using namespace std;

// Iteration method
int factorial_iteration(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

int main() {
    int n = 5;
   
    cout << "Factorial of " << n << " using iteration: " << factorial_iteration(n) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(n)

Space Complexity:O(1)

2 Recursion

The simplest way to solve this problem is by using recursion.

Code Implementation in C++:

#include <iostream>
using namespace std;

// Recursion method
int factorial_recursion(int n) {
    if (n == 0)
        return 1;
    else
        return n * factorial_recursion(n - 1);
}

int main() {
    int n = 5;
    cout << "Factorial of " << n << " using recursion: " << factorial_recursion(n) << endl;
    
    return 0;
}

Complexity Analysis:

Time Complexity:O(n)

Space Complexity:O(n) due to recursive calls

3 Using Tail Recursion

In tail, recursion, the recursive call is the last thing executed by the function.

With tail recursion, the compiler can optimize the code to avoid stack overflow.

Code Implementation in C++:

int factorial(int n, int result = 1) {
    if (n == 0)
        return result;
    else
        return factorial(n - 1, n * result);
}

Complexity Analysis:

Time Complexity:O(n)

Space Complexity:O(1)