Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Computing Factorial Recursively

EASYProblemSolveExternal Links

Description

Given a non-negative integer n, compute its factorial.

The factorial of n, written as n!, is the product of all positive integers from 1 to n:

n! = n × (n − 1) × (n − 2) × ... × 2 × 1

By convention, 0! = 1 (the empty product).

For example:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 3! = 3 × 2 × 1 = 6
  • 1! = 1
  • 0! = 1

Factorials grow extremely fast. Even for small values of n, the result becomes very large (12! = 479,001,600). This problem focuses on computing the factorial using both iterative and recursive techniques, with emphasis on understanding how recursion breaks a problem into smaller subproblems.

Examples

Example 1

Input: n = 5

Output: 120

Explanation: 5! = 5 × 4 × 3 × 2 × 1 = 120. We multiply all integers from 5 down to 1.

Example 2

Input: n = 4

Output: 24

Explanation: 4! = 4 × 3 × 2 × 1 = 24.

Example 3

Input: n = 0

Output: 1

Explanation: By mathematical convention, the factorial of 0 is defined as 1. This is called the "empty product" — when you multiply zero numbers together, the result is the multiplicative identity, which is 1. This also serves as the base case for the recursive solution.

Example 4

Input: n = 1

Output: 1

Explanation: 1! = 1. This is another boundary case — the smallest positive integer's factorial is simply 1 itself.

Constraints

  • 0 ≤ n ≤ 12

Editorial

Brute Force

Intuition

The most straightforward way to compute a factorial is to multiply all integers from 1 to n together, one by one.

Imagine you are building a tower of blocks. You start with 1 block (the base), then double-check your count by multiplying: 1 block × 2 = 2 blocks worth of combinations, then × 3 = 6, and so on. Each step takes the running product and multiplies it by the next integer.

We initialize a variable result to 1 (since multiplying by 1 does not change the value, and this also correctly handles the case n = 0 where the loop does not execute). Then we loop from 2 to n, multiplying result by each integer.

Step-by-Step Explanation

Let's trace through with n = 5:

Step 1: Initialize result = 1. This handles the base case (0! = 1) and acts as the multiplicative identity.

Step 2: i = 2: result = 1 × 2 = 2.

Step 3: i = 3: result = 2 × 3 = 6.

Step 4: i = 4: result = 6 × 4 = 24.

Step 5: i = 5: result = 24 × 5 = 120.

Step 6: Loop ends. Return result = 120.

Iterative Factorial — Multiplying from 2 to N — Watch as the running product grows rapidly by multiplying each successive integer from 2 up to n.

Algorithm

  1. Initialize result = 1
  2. For each integer i from 2 to n:
    • Multiply result by i
  3. Return result

Note: Starting from 2 instead of 1 is a minor optimization — multiplying by 1 has no effect. If n is 0 or 1, the loop does not execute and we correctly return 1.

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int factorial(int n) {
        int result = 1;
        
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        
        return result;
    }
};
class Solution:
    def factorial(self, n: int) -> int:
        result = 1
        
        for i in range(2, n + 1):
            result *= i
        
        return result
class Solution {
    public int factorial(int n) {
        int result = 1;
        
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

The loop runs (n - 1) times, performing one multiplication per iteration. Each multiplication is a constant-time operation, so the total work is proportional to n.

Space Complexity: O(1)

We use a single integer variable result to accumulate the product. No additional data structures are allocated.

Why This Approach Is Not Efficient

The iterative approach is actually very efficient for this problem — O(n) time and O(1) space is hard to beat since we must examine every factor at least once. For the given constraint n ≤ 12, it runs in microseconds.

However, the iterative approach has an educational limitation: it does not teach recursive thinking. Many problems in computer science — tree traversals, divide-and-conquer algorithms, backtracking — require recursion as a fundamental tool. The factorial function is the perfect entry point to learn recursion because:

  1. Natural recursive structure: n! = n × (n-1)!, which directly translates to a function calling itself with a smaller input.
  2. Clear base case: 0! = 1 (or 1! = 1), giving an obvious stopping condition.
  3. Simple enough to trace by hand: Unlike complex recursive algorithms, you can follow every recursive call and return value mentally.

The recursive approach trades O(1) space for O(n) stack space, but the pedagogical value of understanding recursion far outweighs this cost for small n.

Optimal Approach - Recursion

Intuition

Recursion is the technique of solving a problem by breaking it into smaller instances of the same problem. The factorial function has a beautiful recursive structure:

n! = n × (n - 1)!

This says: "to compute the factorial of n, multiply n by the factorial of (n - 1)." But to compute (n-1)!, we need (n-2)!, and so on. This chain of calls continues until we reach the base case: 0! = 1 (or equivalently, 1! = 1).

Think of it like a chain of managers delegating work:

  • The CEO (factorial(5)) says: "I need 5 × whatever factorial(4) returns."
  • The VP (factorial(4)) says: "I need 4 × whatever factorial(3) returns."
  • The Director (factorial(3)) says: "I need 3 × whatever factorial(2) returns."
  • The Manager (factorial(2)) says: "I need 2 × whatever factorial(1) returns."
  • The Worker (factorial(1)) says: "I know this one! It's 1."

Now the answers flow back up the chain:

  • factorial(1) returns 1
  • factorial(2) returns 2 × 1 = 2
  • factorial(3) returns 3 × 2 = 6
  • factorial(4) returns 4 × 6 = 24
  • factorial(5) returns 5 × 24 = 120

Each recursive call pushes a new frame onto the call stack, and when a call returns, its frame is popped. This is why recursion uses O(n) space — there are n frames on the stack simultaneously at the deepest point.

Step-by-Step Explanation

Let's trace factorial(5) through the entire recursion:

Step 1: Call factorial(5). Is n == 0 or n == 1? No (n = 5). So we need to compute 5 × factorial(4). We pause and call factorial(4).

Step 2: Call factorial(4). Is n == 0 or n == 1? No (n = 4). We need 4 × factorial(3). Pause and call factorial(3).

Step 3: Call factorial(3). Is n == 0 or n == 1? No (n = 3). We need 3 × factorial(2). Pause and call factorial(2).

Step 4: Call factorial(2). Is n == 0 or n == 1? No (n = 2). We need 2 × factorial(1). Pause and call factorial(1).

Step 5: Call factorial(1). Is n == 0 or n == 1? YES (n = 1). This is our base case. Return 1. No more recursive calls needed.

Step 6: Back in factorial(2): we now have factorial(1) = 1. Compute 2 × 1 = 2. Return 2.

Step 7: Back in factorial(3): we now have factorial(2) = 2. Compute 3 × 2 = 6. Return 6.

Step 8: Back in factorial(4): we now have factorial(3) = 6. Compute 4 × 6 = 24. Return 24.

Step 9: Back in factorial(5): we now have factorial(4) = 24. Compute 5 × 24 = 120. Return 120.

Result: factorial(5) = 120.

Recursive Factorial — Call Stack Unwinding — Watch how factorial(5) breaks into a chain of recursive calls, dives down to the base case, and then returns results back up the chain.

Algorithm

  1. Base case: If n == 0 or n == 1, return 1
  2. Recursive case: Return n × factorial(n - 1)

The recursion naturally terminates because each call reduces n by 1, and eventually n reaches 1 (or 0), hitting the base case.

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int factorial(int n) {
        // Base case: 0! = 1! = 1
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
};
class Solution:
    def factorial(self, n: int) -> int:
        # Base case: 0! = 1! = 1
        if n == 0 or n == 1:
            return 1
        
        # Recursive case: n! = n * (n-1)!
        return n * self.factorial(n - 1)
class Solution {
    public int factorial(int n) {
        // Base case: 0! = 1! = 1
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
}

Complexity Analysis

Time Complexity: O(n)

The function makes exactly n recursive calls (from factorial(n) down to factorial(1)). Each call performs a constant amount of work (one comparison and one multiplication), so the total time is O(n).

Space Complexity: O(n)

Each recursive call adds a frame to the call stack. At the deepest point (when factorial(1) is called), there are n frames on the stack simultaneously. Once the base case returns, the frames are popped one by one as results flow back up.

This is the key trade-off compared to the iterative approach: we use O(n) extra space for the call stack instead of O(1). For n ≤ 12, this is negligible, but for very large n, deep recursion could cause a stack overflow.