Recursion & the call stack

Base case, recursive case, and how each call lives on the stack until it returns. · 8 min read

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursion needs two parts: a base case that stops the recursion, and a recursive case that makes progress toward it.

The three-question checklist

Before trusting a recursive function, ask:

What is the smallest input I can answer immediately? That is the base case.
How does each call make the problem smaller? That is the progress measure.
How do smaller answers combine into the current answer? That is the return step.

If any one of these is vague, the recursion is probably wrong.

def factorial(n):
    if n == 0:        # base case
        return 1
    return n * factorial(n - 1)   # recursive case

Factorial goes down first, then returns upward

factorial(4) — Needs 4 × factorial(3).
factorial(3) — Needs 3 × factorial(2).
factorial(2) — Needs 2 × factorial(1).
factorial(1) — Needs 1 × factorial(0).
factorial(0) = 1 — Base case returns, then the stack unwinds.

Result: 4 × 3 × 2 × 1 = 24

Each call gets its own stack frame holding its local variables. Calls push on the way down and pop (returning a value) on the way back up — last in, first out, exactly like a stack:

Interactive visualization: Call stack — push on call, pop on return — step through it frame by frame on this page.

Another small example: sum an array

A recursive sum peels off one item and asks the smaller question: what is the sum of the rest?

def sum_array(a, i=0):
    if i == len(a):
        return 0
    return a[i] + sum_array(a, i + 1)

There are n calls, each does constant work, so time is O(n). The call stack also reaches depth n, so auxiliary space is O(n).

When recursion branches

When a function makes two recursive calls (like merge sort, or naive Fibonacci), the calls branch into a tree — and the shape of that tree is exactly what the complexity derivations in the sorting chapter measured.

Interactive visualization: Two recursive calls branch into a tree — step through it frame by frame on this page.