Recursion and the call stack
Recursion solves a problem by expressing it in terms of smaller instances of itself. Every recursive function needs two things: a base case that stops the descent, and a recursive case that provably moves toward it.
The visualizer draws the call stack as frames pile up and unwind, which is the mental model that makes recursion click — each frame holds its own local state, and the return value flows back up through the parents that are waiting.
Time and space complexity
| Pattern | Time | Space | Example |
|---|---|---|---|
| Linear recursion | O(n) | O(n) stack | Factorial, list length |
| Binary recursion | O(2ⁿ) | O(n) stack | Naive Fibonacci |
| Divide and conquer | O(n log n) | O(log n) stack | Merge Sort |
| Memoised recursion | O(n) | O(n) table + stack | Top-down DP |
| Tail recursion | O(n) | O(1) if optimised | Accumulator style |
How to use this visualizer
Choose a recursive problem such as factorial, Fibonacci, or Towers of Hanoi.
Step forward and watch new frames stack on each call.
Reach the base case and watch values return back up the stack.
On naive Fibonacci, spot the repeated subtrees that memoisation eliminates.
Frequently asked questions
Each call reserves a stack frame for its parameters, locals, and return address. If the base case is missing, unreachable, or the recursion simply goes deeper than the stack allows — often a few thousand frames — the stack runs out of space and the program crashes. Fix it by ensuring the base case is reachable, or convert the recursion to an explicit loop with your own stack.
Both repeat work, but recursion delegates state to the call stack while iteration keeps state in explicit variables. Recursion expresses tree- and graph-shaped problems far more naturally; iteration avoids per-call overhead and stack-depth limits. Any recursion can be rewritten iteratively with an explicit stack, though clarity often suffers.
A call is tail recursive when the recursive call is the very last operation, with nothing left to compute after it returns. Because the parent frame has no remaining work, a compiler can reuse it instead of allocating a new one, reducing stack usage to O(1). Scheme and Scala guarantee this optimisation; JavaScript engines and CPython generally do not.