Recursion & the Call Stack — Data Structures Course

What you'll learn

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It's the natural way to work with trees, graphs, and divide-and-conquer algorithms — but to use it well you have to understand the call stack that runs it.

By the end you'll be able to:

Write a recursive function with a correct base case and recursive case
Trace how the call stack grows and unwinds
Read a recursion tree and spot repeated work
Convert between recursion and iteration, and avoid stack overflow

Anatomy of recursion

Every correct recursive function has two parts:

Base case — the smallest input, solved directly, with no further recursion. It's what stops the recursion.
Recursive case — solves the problem in terms of a smaller subproblem, moving toward the base case.

Language

factorial.py

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

Watch out

Forget the base case, or fail to shrink the input, and the function recurses forever — until the call stack fills up and the program crashes with a stack overflow.

The call stack

Each function call gets a stack frame holding its arguments and where to return. Calls push frames on top; returns pop them off — strictly last-in, first-out. Step through factorial(4) and watch the stack build up to the base case, then unwind as each call multiplies and returns:

factorial(4) on the call stack

Tracing factorial(4)

Call stack

factorial(4)

4 > 1 → 4 × factorial(3)

1/8Call factorial(4). Because 4 > 1, it must compute 4 × factorial(3) first.

Blue = running · grey = paused, waiting · green = returning a value.

Key idea

The deepest call finishes first. Recursion "pauses" each call on the stack, dives to the base case, then resolves everything on the way back up.

Recursion trees

When a function calls itself more than once, the calls form a tree. This is how you reason about a recursive algorithm's total cost — count the nodes. Here's the naive Fibonacci fib(n) = fib(n-1) + fib(n-2):

The fib(4) recursion tree

fib(4)

fib(3)

fib(2)

fib(1)=1fib(0)=0

fib(1)=1

fib(2)

fib(1)=1fib(0)=0

Each call spawns two more until it hits a base case. Notice fib(2) is computed twice — naive recursion repeats work, which is why it's O(2ⁿ).

Recursion vs iteration

Anything recursive can be rewritten with a loop, and vice-versa. Recursion is often clearer for naturally-nested data (trees!); iteration avoids the call-stack overhead. Here's factorial as a plain loop — same result, constant stack space:

Language

factorial_iter.py

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Pitfalls & memoization

The Fibonacci tree above recomputes fib(2) and friends many times — exponential wasted work. The fix is memoization: cache each result the first time you compute it, turning O(2ⁿ) into O(n). We'll lean on this idea again in dynamic-programming graph algorithms later.

Tip

Deep recursion can overflow the stack (Python caps at ~1000 frames by default). For very deep problems, prefer iteration or an explicit stack — a technique you'll use for graph traversal in Phase 6.

Recap & quick check

Key takeaways

A recursive function needs a base case (stops it) and a recursive case (shrinks toward the base).
Each call gets a stack frame; calls push, returns pop — last-in, first-out.
The deepest call resolves first; the stack then unwinds back to the top.
Multiple self-calls form a recursion tree whose node count is the total work.
Missing base cases cause stack overflow; memoization removes repeated work.

Quick check

1. What does the base case do in a recursive function?

2. In factorial(4), which call returns first?

3. Why is naive recursive Fibonacci O(2ⁿ)?

4. What causes a stack overflow?

You can now measure cost and think recursively — the two tools you'll use on every structure ahead. Next up: Module 4 — Arrays & Dynamic Arrays.