Factorial & the Call Stack
Frames push down to the base case, answers unwind back up
Recursion solves a problem by calling itself on a smaller input and trusting that smaller answer. The hidden machinery is the call stack: every call pushes a frame holding its paused work, and answers flow back as frames pop in reverse order. Each cell here is one stack frame — watch them pile up to the base case, then unwind carrying the products home.
Details
Animated on: Compute factorial(5) = 5 x 4 x 3 x 2 x 1 recursively, watching the call stack grow to depth 5 and then unwind.
Problem:Factorials of LargeMedium
Frames push down to the base case, answers unwind back up
step 1 / 11
Call factorial(5). A frame for it is pushed onto the call stack — the stack is how the program remembers who is waiting for whom.
- top=0· arr[0] = f(5)
1FUNCTION factorial(n):2 IF n == 1:3 RETURN 1 (base case — stops the descent)4 (pause here until the smaller call answers)5 RETURN n * factorial(n - 1)6call factorial(5)
← / → step · space play · Home restart
Every step in words
Show all 11 steps
- Call factorial(5). A frame for it is pushed onto the call stack — the stack is how the program remembers who is waiting for whom.
- n=5 is not 1, so f(5) hits 'return 5 * factorial(4)' — it cannot multiply yet. It pauses mid-expression and pushes f(4) on top.
- Same story one level down: n=4 is not the base case either, so f(4) pauses at '4 * factorial(3)' and pushes f(3). Every paused multiply is saved in its frame.
- n=3 still is not 1 — push f(2). Notice nothing has been multiplied yet: recursion defers ALL the work until the base case finally answers.
- n=2 pushes f(1). The stack is now 5 frames deep — this maximum depth is exactly why recursion costs O(n) space.
- Base case! n=1, so f(1) returns 1 immediately — no new call. Without this floor the pushes would never stop and the stack would overflow.
- f(1)'s frame pops and its 1 lands in f(2)'s paused expression: 2 * 1 = 2. The unwind has begun — answers now travel back down the stack.
- f(2) pops, returning 2 to f(3): 3 * 2 = 6. The multiplies happen in REVERSE call order — deepest frame first, on the way back up.
- f(3) pops, returning 6 to f(4): 4 * 6 = 24. Each returning frame does its one deferred multiply — O(n) time overall.
- f(4) pops, returning 24 to f(5): 5 * 24 = 120. The very first call made is the LAST one to finish its multiply.
- f(5) pops and the stack is empty again. factorial(5) = 5·4·3·2·1 = 120 — the stack grew 5 frames deep, then unwound back to zero carrying the answer.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.