Factorial of N: The Recursion Pattern That Teaches the Call Stack

Factorial is the problem that finally makes recursion click. The prompt is tiny — compute n! — but solving it recursively forces you to hold two ideas at once: a rule that shrinks the problem, and a base case that stops it. Get those two right and you have the template behind every recursive algorithm you'll write later, from tree traversals to divide-and-conquer.

The definition is a gift, because it's already recursive. 5! = 5 × 4 × 3 × 2 × 1, and 4! = 4 × 3 × 2 × 1, so 5! = 5 × 4!. The bigger factorial contains the smaller one. That single observation is the whole solution.

The problem#

Given a non-negative integer n, return n! — the product of every integer from 1 up to n. By definition 0! = 1 and 1! = 1.

Two facts anchor everything below:

• The base case is n ≤ 1, where the answer is simply 1 — no more multiplying to do.
• Every other case reduces to a smaller, identical sub-problem: n! = n × (n − 1)!.

The brute force baseline#

You can compute a factorial with a plain loop — no recursion at all.

This is genuinely fine — it runs in O(n) time and O(1) space, and in production code it's the version you'd ship. But it hides the structure the problem is trying to teach. The loop grinds out a number without ever exposing why n! = n × (n − 1)!. For an interview about recursion, the loop dodges the exact skill being tested: expressing a problem in terms of a smaller version of itself and trusting the call stack to assemble the pieces.

The key insight: define the problem in terms of itself#

Recursion works when three conditions hold, and factorial satisfies all three cleanly:

1. A base case that returns an answer with no further recursion — here, n ≤ 1 returns 1.
2. A recursive case that does a little work and delegates the rest to a smaller call — here, n × factorial(n − 1).
3. Progress toward the base case on every call — n − 1 is strictly smaller, so you always march down to 1.

The number 1 isn't chosen arbitrarily as the base answer. It's the identity for multiplication: multiplying by 1 changes nothing, so it's the safe seed that lets the chain n × (n−1) × … × 1 terminate without distorting the product. That's why n ≤ 1 returns 1 rather than 0 — a 0 would collapse the entire product to zero.

The mental model that saves you: don't trace the whole thing in your head. Trust that factorial(n − 1) returns the correct answer for n − 1, multiply it by n, and you're done. Recursion is a promise you make to yourself and keep one level at a time.

The optimal solution#

Here is the exact implementation the visualizer steps through:

Four lines, and every one earns its place. The if (n <= 1) return 1 is the floor that stops the descent — delete it and the calls run factorial(0), factorial(-1), factorial(-2)… forever, until the engine throws Maximum call stack size exceeded. The return n * factorial(n - 1) is the recursive case: it can't finish until the inner call resolves, so it defers its multiplication and dives deeper first.

That deferral is the heart of it. On the way down, nothing gets multiplied — each frame just parks its n and waits. Only when the base case fires does the chain reverse and the products get computed on the way back up.

Walkthrough: n = 4#

Follow the call stack as it grows downward, hits the base case, then unwinds upward. factorial(4) should return 24.

Read it top to bottom, then bottom to top. The first four rows push frames onto the stack — four calls stacked up, none of them finished. The base-case row is the pivot: factorial(1) returns 1 with no further recursion, and that unblocks everyone above it. The last three rows pop frames off, each multiplying the child's result by its own n: 1 → 2 → 6 → 24. The stack depth reaches 4 at its deepest, which is exactly the space cost.

Complexity#

Both do the same n − 1 multiplications, so time is O(n) either way. The difference is space: recursion holds n frames on the call stack simultaneously — one per pending multiplication — so its memory grows linearly with n. The loop keeps a single accumulator, giving O(1) space. That's the classic recursion-versus-iteration trade: clarity of expression paid for in stack memory.

Common mistakes#

• Forgetting the base case. No if (n <= 1) means infinite recursion and a stack-overflow crash. The base case isn't optional decoration — it's what makes the recursion terminate.
• Using n == 0 instead of n <= 1. Testing n == 0 alone still works for 0!, but n <= 1 is cleaner: it covers both 0 and 1 and guards against negative inputs falling through the base case.
• Returning 0 from the base case. Multiplication's identity is 1, not 0. Seed the chain with 0 and every factorial collapses to zero.
• Ignoring overflow. JavaScript numbers lose integer precision past 2^53, so factorials beyond 21! come back wrong. For large n, reach for BigInt.
• Assuming the multiply happens on the way down. It doesn't. Each frame defers its multiplication until the deeper call returns — the products are all computed while the stack unwinds.

Where this pattern shows up next#

The "base case plus one recursive step" template generalizes far past factorial:

• Sum of First N Numbers — the same shape with + instead of ×, and 0 as the identity base case.
• Sum of All Numbers in Array — recursion that shrinks an array by one element per call instead of decrementing a counter.
• Power of Two — halving toward a base case, the multiplicative cousin of counting down.
• Recursion Masterclass — the full framework for base cases, recursive cases, and reading a call stack.

You can also step through Factorial of N interactively to watch the call stack grow on the descent, hit the base case, and unwind while the products flow back up.

FAQ#

Why does the base case return 1 instead of 0?#

Because 1 is the identity element for multiplication — multiplying any number by 1 leaves it unchanged, so it's the neutral seed that lets the product chain terminate cleanly. Returning 0 would poison the entire computation, since anything multiplied by 0 is 0, making every factorial come out as zero regardless of n.

What is the time and space complexity of recursive factorial?#

Time is O(n): computing n! requires n − 1 multiplications, one per recursive call. Space is O(n) as well, because the recursion holds n stack frames alive at its deepest point — every deferred multiplication waits on the frame below it. The iterative loop version matches the O(n) time but needs only O(1) space since it keeps a single running product.

What happens if you forget the base case?#

The recursion never stops. Without if (n <= 1) return 1, each call spawns another with an ever-smaller n — factorial(0), factorial(-1), and so on downward — and the call stack keeps growing until the JavaScript engine runs out of room and throws "Maximum call stack size exceeded." The base case is the single line that turns infinite recursion into a terminating algorithm.

When should I use recursion instead of a loop for factorial?#

For raw performance, use the loop — it avoids the O(n) call-stack overhead and can't overflow the stack. Recursion earns its place when clarity matters more than micro-efficiency, or when you're learning the pattern: factorial's recursive form mirrors its mathematical definition (n! = n × (n − 1)!) almost letter for letter, which is why it's the canonical first example for understanding how the call stack defers and resolves work.