Step by step
The example above, written out — the same steps the animation plays.
- 1factorial(5). factorial(5) = 5 × factorial(4) … until factorial(1), which is simply 1.
- 2Call factorial(5). factorial(5) needs factorial(4) first, so it waits — a new frame goes on the stack.
- 3Call factorial(4). factorial(4) needs factorial(3) first, so it waits — a new frame goes on the stack.
- 4Call factorial(3). factorial(3) needs factorial(2) first, so it waits — a new frame goes on the stack.
- 5Call factorial(2). factorial(2) needs factorial(1) first, so it waits — a new frame goes on the stack.
- 6Call factorial(1). factorial(1) is the base case: it returns 1 without calling anything.
- 7factorial(1) returns 1. Base case returns 1. Now the waiting calls finish, newest first.
- 8factorial(2) returns 2. 2 × 1 = 2. Its frame leaves the stack.
- 9factorial(3) returns 6. 3 × 2 = 6. Its frame leaves the stack.
- 10factorial(4) returns 24. 4 × 6 = 24. Its frame leaves the stack.
- 11factorial(5) returns 120. 5 × 24 = 120. Its frame leaves the stack.
- 12factorial(5) = 120. 5 calls went down, 5 returns came back up. The stack is empty again.
What's happening?
- Every call that is not the base case waits for a smaller call — and each waiting call is a frame on the call stack.
- The base case answers without calling anything, and that is what stops the recursion.
- Then the frames come off the stack newest first, each finishing its own work with the answer from below.
Complexity
- Time
- O(n) calls for factorial(n)
- Space
- O(n) stack frames
Where you'll meet it
Tree and graph traversal, file-system walks, parsers, divide-and-conquer algorithms like merge sort, and backtracking.
Common mistake
A missing or unreachable base case: the stack keeps growing until the program crashes with a stack overflow.
FAQ
What is a base case?
The input small enough to answer directly, without another call. Every recursion needs one.
Why does deep recursion cause a stack overflow?
Each waiting call keeps a frame on the call stack; too many frames exhaust the memory set aside for it.
Is recursion slower than a loop?
Often slightly, because of the extra frames — but for trees and graphs it is usually far clearer.