Factorial
Factorial multiplies n by the factorial of n − 1, treating 0 as the base case whose factorial is 1 by definition. Every call above the base case makes exactly one further call, so the recursion forms a single chain rather than a tree.
When it is the right choice
Factorial is the standard first example of recursion precisely because it has nothing else going on: no branching, no repeated work, no state to restore. It is not how a real program should compute a factorial past a tiny n — an iterative loop does the same job without building a stack frame per value, and the recursive version overflows the call stack long before it overflows the numeric type it returns into. Its value here is entirely in what it shows about the stack itself.
How it works
- Call factorial with the given n.
- If n is 0, the base case is reached: hand back 1 without recursing further.
- Otherwise, call factorial on n − 1 and wait for it to answer.
- Multiply n by that answer and hand the product back to whichever call is waiting for it.
Worth noticing
- The stack grows to exactly n + 1 frames before the first value comes back — nothing returns until the base case is reached, so the stack view fills up completely before it starts unwinding.
- Depth and call count are the same number here, which is easy to assume always holds; this page's neighbour, Towers of Hanoi, shows a depth of n producing far more than n calls.
- It is the cleanest algorithm to trace by hand precisely because it never branches and never has to undo anything.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Extra space
- O(n)
- Largest input
- n = 20
The largest input is a pedagogical ceiling rather than a technical one. This algorithm makes n + 1 calls, and past n = 20 the run stops being something a person can sit and watch — long before it reaches the step limit the tool enforces.