Find Factorial Using Recursion - Java

Category: Medium | Concepts used: Recursion, base cases, iterative alternative

---

Problem Statement

Given a number n, compute its factorial (n! = n × (n-1) × (n-2) × ... × 1) using recursion.

Input : n = 5      Output: 120   (5×4×3×2×1)
Input : n = 0        Output: 1     (0! is defined as 1)

Examples (with edge scenarios)

#	n	Output	Why
1	5	120	5×4×3×2×1
2	0	1	By mathematical definition, 0! = 1 — a classic edge case
3	1	1	Base case, trivially 1
4	-3 (negative)	Undefined	Factorial isn’t defined for negative numbers — must handle explicitly
5	20 (large n)	Overflow risk	20! already exceeds Long.MAX_VALUE’s safe range in some contexts — worth mentioning

Common Fresher Mistake

Mistake	What happens	Fix
Forgetting the base case entirely	Infinite recursion → StackOverflowError	Always define n <= 1 (or n == 0) as the base case that stops recursion
Not validating negative input	Recursion never terminates (keeps decrementing below 0 forever) or produces nonsensical results	Explicitly check n < 0 and throw/handle before recursing
Using int for large factorials	Silent overflow for n beyond ~12-13 (since int max is ~2.1 billion)	Use long, or BigInteger for very large n

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether zero and negative values are allowed, how large the input can be, and what should happen when an arithmetic result exceeds the chosen Java type. The examples use the contract stated in this article, but an interview answer should say these assumptions aloud.

Analogy: Matryoshka Nesting Dolls

Imagine you have a series of Matryoshka nesting dolls:

• You want to find out how much sand is inside a large doll size 5 (factorial(5)).
• The label on doll 5 says: “My weight is 5 times the weight of doll 4 (5 * factorial(4)).”
• To find doll 4’s weight, you open it up. Doll 4 says: “My weight is 4 times the weight of doll 3 (4 * factorial(3)).”
• You continue opening dolls until you reach the smallest, solid doll size 1 (the base case factorial(1)).
• Doll 1 is solid and does not open — its weight is simply 1 kg.
• Now you can close them back up, multiplying the weights as you go:
  • Doll 2’s weight is 2 * 1 = 2 kg.
  • Doll 3’s weight is 3 * 2 = 6 kg.
  • Doll 4’s weight is 4 * 6 = 24 kg.
  • Doll 5’s weight is 5 * 24 = 120 kg!

---

Solution 1 — Simple Recursion

Intuition

Factorial has a natural recursive definition: n! = n × (n-1)!. So to compute 5!, we just need 4! (and then multiply by 5); to get 4!, we need 3!; and so on, until we hit the known base case 1! = 1 (or 0! = 1), at which point the chain of multiplications can be resolved back up.

public class FactorialRecursive {
    public static long factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial is not defined for negative numbers");
        }
        if (n == 0 || n == 1) {
            return 1; // base case
        }
        return n * factorial(n - 1); // recursive case
    }

public static void main(String[] args) {
        System.out.println(factorial(5));  // 120
        System.out.println(factorial(0));   // 1
        System.out.println(factorial(1));    // 1
    }
}

Output:

120
1
1

Dry Run (n = 4)

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1                  (base case reached)

Unwinding:
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Final: 24

Interviewer’s take

This is the expected, textbook solution — clean and directly mirrors the mathematical definition. The base case and negative-number check are the two details interviewers specifically watch for; missing either is a common trip-up.

Follow-up questions you might get:

• “What happens if you forget the base case?” → Infinite recursion, eventually causing a StackOverflowError since the call stack keeps growing without ever “returning.”
• “What’s the space complexity here?” → O(n) — each recursive call adds a new frame to the call stack, and there are n calls before hitting the base case.
• “How would you handle very large n where the result overflows long?” → Use java.math.BigInteger, which supports arbitrarily large numbers.

---

Solution 2 — Iterative Approach (For Comparison)

Intuition

Instead of letting the call stack track the “unwinding” multiplications, just keep a running product and multiply it by each number from 1 up to n directly in a loop — same math, no recursive call stack needed.

public class FactorialIterative {
    public static long factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial is not defined for negative numbers");
        }
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(factorial(5)); // 120
    }
}

Output:

120

Dry Run (n = 4)

result=1
i=2: result=1*2=2
i=3: result=2*3=6
i=4: result=6*4=24
Final: 24

Interviewer’s take

Since the question specifically asks for recursion, this iterative version is more of a “bonus comparison” than the primary answer — but it’s great to mention the trade-off: the iterative version uses O(1) space (no call stack growth), while the recursive version uses O(n) space. Good to bring up proactively when discussing recursion’s costs.

---

📊 Visual Recursive Stack (Winding vs Unwinding)

graph TD
    subgraph Winding Phase
        F5["factorial(5)"] -->|Calls| F4["factorial(4)"]
        F4 -->|Calls| F3["factorial(3)"]
        F3 -->|Calls| F2["factorial(2)"]
        F2 -->|Calls| F1["factorial(1)"]
    end
    subgraph Unwinding Phase
        F1 -->|Returns 1| F2
        F2 -->|Returns 2 * 1 = 2| F3
        F3 -->|Returns 3 * 2 = 6| F4
        F4 -->|Returns 4 * 6 = 24| F5
        F5 -->|Returns 5 * 24 = 120| Result["Result: 120"]
    end

---

Final Verdict — Which Solution Should You Give?

• Solution 1 (recursion) is the expected answer, since the question specifically asks for it.
• Mention Solution 2 (iterative) as a natural follow-up when discussing space complexity trade-offs — this shows you understand recursion isn’t always the most memory-efficient choice, even when it’s elegant.

---

Quick Recap

Approach	Time	Space	Interview Signal
Recursive	O(n)	O(n) call stack	Expected, matches the question’s ask
Iterative	O(n)	O(1)	Good comparison point for space trade-offs