Recursion and the call stack

Algorithms · Design techniques

Recursion and the call stack

Recursion turns a problem into smaller copies of itself. The code may be short, but execution builds a concrete structure of calls, local variables and suspended results.

Thinking recursively

You do not need to imagine every call at once. Assume the function can solve a smaller instance, then use that result to build the current solution.

Base case

An instance solved directly, without another call.

Recursive step

Shrinks the problem and combines the returned result.

Progress

Every call must genuinely move toward the base case.

Two directions. Calls are created on the way down; results are returned and combined on the way up. Mixing these directions is a common source of confusion.

Why recursion terminates and is correct

The base case is correct. For example, 0! = 1 and 1! = 1.
A measure decreases. In fact(n), the parameter changes from n to n−1 and has a lower bound.
The step preserves correctness. If fact(n−1) is correct, multiplying it by n produces n!.

This mirrors mathematical induction: a base case, an assumption about a smaller problem and an inductive step.

What the call stack contains

Every suspended call occupies a frame. A frame stores parameters, local variables, the return location and space for the return value. The stack is LIFO: the most recent call is the first to finish.

Stack topfact(2)n = 2 · waiting fact(1)

fact(3)n = 3 · waiting fact(2)

fact(4)n = 4 · waiting fact(3)

The newest call is on top ↑

Stack overflow. The stack is finite. A recursion without progress—or simply one that is too deep—eventually runs out of frames.

Lab: follow every call

Choose an example and advance one operation at a time. The tree shows all calls; the stack shows only the active chain at that instant.

n = 5

All calls

Execution tree

scroll if needed

Active calls only

Call stack

Speed1×

Calls: 0
Maximum depth: 0
Active frames: 0
Cache hit: 0

fact(n)
if n ≤ 1
return 1
return n · fact(n − 1)

current operation suspended call returned result cache hit

Factorial: a single chain of calls

Definition

0! = 1
n! = n · (n−1)! for n > 0

Time

T(n) = T(n−1) + Θ(1) = Θ(n). One call for every value from n to 1.

Space

Θ(n) simultaneous frames before unwinding begins.

For fact(5), descent builds 5 · fact(4), then 4 · fact(3), and so on. Multiplication only starts at the base case: 1, 2, 6, 24, 120.

Fibonacci: a tree with repeated work

Definition

F₀ = 0, F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂

Naive time

T(n) = T(n−1) + T(n−2) + Θ(1) = Θ(φⁿ), where φ ≈ 1.618.

Naive space

Θ(n): the tree is large, but only one path is live on the stack at a time.

Tree ≠ stack. The tree counts all calls performed; the stack measures the depth of calls still open. For fib(n), total calls are 2Fₙ₊₁−1, while depth is only Θ(n).

Memoization: remember instead of recomputing

Fibonacci recomputes fib(3), fib(2) and the same base cases many times. A cache indexed by n turns every repeated subproblem into a constant-time lookup. Enable “Use memoization” in the lab: purple nodes finish by reading a known result.

Naive recursionΘ(φⁿ)

time · Θ(n) stack

With memoizationΘ(n)

time · Θ(n) stack + cache

Optimized iterationΘ(n)

time · Θ(1) space

When to use recursion and when to iterate

Prefer recursion	Prefer iteration
The structure is naturally recursive: trees, directories, divide and conquer, backtracking.	Depth may be very large or depends on untrusted input.
The code directly mirrors a definition and remains easier to verify.	A compact repeated state exists, such as only two consecutive Fibonacci values.
Depth is logarithmic or otherwise controlled.	Call overhead and stack memory matter.

Tail recursion is not an automatic fix: JavaScript and PHP do not generally guarantee elimination of recursive frames. If depth can be high, use a loop or an explicit stack.

Common mistakes

Missing or unreachable base case: calls continue until stack overflow.
No progress: f(n) calls f(n) or moves n away from the base case.
Confusing return values and effects: printing a result is not the same as returning it to the previous call.
Ignoring repeated subproblems: naive Fibonacci looks short but creates exponentially many calls.
Forgetting the stack in space analysis: a function with no auxiliary arrays is not necessarily Θ(1) in memory.