Trace a Recursive Factorial
You call factorial(5). Each recursive call pushes a new frame onto the call stack. When the base case is reached, the frames pop in reverse order, each multiplying its result by n.
1. Push factorial(5) frame, n = 5
factorial(5) is called. A new stack frame is pushed with n = 5. The function checks: is n == 0? No. It calls factorial(4).
2. Push factorial(4) frame, n = 4
factorial(4) is called. A new frame is pushed with n = 4. Is n == 0? No. Calls factorial(3).
3. Push factorial(3) frame, n = 3
factorial(3) is called. A new frame is pushed with n = 3. Is 3 == 0? No. Calls factorial(2).
4. Push factorial(2) frame, n = 2
factorial(2) is called. A new frame is pushed with n = 2. Is 2 == 0? No. Calls factorial(1).
5. Push factorial(1) frame, n = 1
factorial(1) is called. A new frame is pushed with n = 1. Is 1 == 0? No. Calls factorial(0).
6. Push factorial(0) frame — base case reached
factorial(0) is called. A new frame is pushed with n = 0. Is 0 == 0? Yes — base case! It returns 1 immediately without further recursion.
7. Return 1 from factorial(0) to factorial(1)
The return value 1 from factorial(0) flows back to factorial(1). It computes 1 × 1 = 1 and returns 1.
8. Return 1 from factorial(1) to factorial(2)
factorial(1) returned 1 to factorial(2). It computes 2 × 1 = 2 and returns 2.
9. Return 2 from factorial(2) to factorial(3)
factorial(2) returned 2 to factorial(3). It computes 3 × 2 = 6 and returns 6.
10. Return 6 from factorial(3) to factorial(4)
factorial(3) returned 6 to factorial(4). It computes 4 × 6 = 24 and returns 24.
11. Return 24 from factorial(4) to factorial(5)
factorial(4) returned 24 to factorial(5). It computes 5 × 24 = 120 and returns 120.
12. Return 120 from factorial(5) to caller
factorial(5) returns 120 as the final result. All five stack frames have been popped.
Why This Matters
The recursion built up 5 stack frames during the descent (factorial 5 down to 0), then unwound them during the ascent (factorial 0 up to 5). Each frame multiplied its n by the return value of the frame below it. The maximum stack depth was 6 (including factorial(0)), so the space complexity is O(n) — the stack depth equals the recursion depth.