🧩 Data Structures & Algorithms · Chapter 9

Recursion

A function that calls itself sounds like a bug. Done right, it is the shortest correct answer to every problem shaped like a tree.

Study this lesson free in the app →

The basics

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem is so small the answer is obvious.

The problem it solves: some problems are made of smaller copies of themselves. A folder contains folders. A family tree contains family trees. 5! is 5 × 4!. Writing a loop for a shape whose depth you don't know in advance is painful; recursion lets you describe one level and trust it for the rest.

The mental model: you're in a dark cinema and want to know your row number. You ask the person in front; they ask the person in front of them, and so on. The person in row 1 knows the answer without asking. Then each answer comes back one row at a time, plus one.

Cost: every pending call sits on the call stack, so recursion depth d costs O(d) extra space. Time = number of calls × work per call.

Explained

Count the files in a folder that has folders inside it, that have folders inside them — you don't know how deep it goes.

A loop needs you to know the shape. Recursion only needs you to handle one folder and trust the same function with each sub-folder. Ten lines, any depth.

Which row am I in?

The cinema is dark and you can't see the row numbers.

You tap the person in front: "Which row are you in?" They don't know either, so they tap the person in front of them. The question travels forward, one row at a time.

The person in row 1 has no one in front. They just say "1" — that's the base case.

Now the answers travel back: "2", "3", … each person adding one to what they heard. While they wait, everyone is paused mid-question — that pile of waiting people is the call stack. A cinema with 2,000 rows would exhaust everyone's patience; a Python program with 2,000 nested calls exhausts its stack.

The two parts and the stack

Every correct recursive function has:

1. Base case — returns an answer directly, no call. if n <= 1: return 1
2. Recursive case — calls itself on a strictly smaller input and combines the result. return n * fact(n - 1)

When fact(4) runs, it can't finish until fact(3) returns, so it is paused on the call stack:

fact(1)  ← base case, returns 1
fact(2)  waiting: 2 * ?
fact(3)  waiting: 3 * ?
fact(4)  waiting: 4 * ?

Then the stack unwinds: 1 → 2 → 6 → 24.

Time = calls × work per call → fact(n) is O(n). Space = deepest the stack gets → O(n).

The call tree of fib(5)

fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. Watch how often fib(2) and fib(3) are recomputed: 15 calls to produce the answer 5. Each extra n multiplies the work by about 1.6 — try n = 7 (41 calls).

Same tree, with a memo

Now every result is written into a dictionary the first time it's computed. The second time fib(3) is asked for, the answer is looked up, so whole branches vanish: 9 calls instead of 15, and only 6 of them — fib(0)…fib(5), each once — do real work: O(n) time, O(n) space for the memo and the stack.

Three shapes in Python

# 1. Linear: one call per level → O(n) time, O(n) stack
def total(nums, i=0):
    if i == len(nums):          # base case
        return 0
    return nums[i] + total(nums, i + 1)   # pass an index, don't slice

# 2. Nested data of unknown depth
def count_items(box):           # box = list that may hold lists
    n = 0
    for x in box:
        n += count_items(x) if isinstance(x, list) else 1
    return n

count_items([1, [2, 3], [[4], 5]])   # 5

# 3. Halving: O(log n) calls
def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)     # compute once, use twice
    return half * half if n % 2 == 0 else half * half * x

power(2, 10)   # 1024, in 5 levels instead of 10 multiplications

Counting the cost

Draw the recursion tree; the cost is in its shape.

pattern                 calls      time       space (stack)
─────────────────────────────────────────────────────────
fact(n)  one branch     n          O(n)       O(n)
power(x,n) halves       log n      O(log n)   O(log n)
merge sort  2 halves    2n         O(n log n) O(n)
naive fib  2 branches   ~1.6ⁿ      O(2ⁿ)      O(n)
memo fib                2n−1       O(n)       O(n)

fib(30) naively makes about 2.7 million calls; fib(50) would make about 40 billion. With a memo, fib(50) is 99 calls.

Space is the depth, not the number of calls: naive fib makes exponentially many calls, but only one root-to-leaf path is paused at any moment.

Gotchas

• No base case, or one the input can skip past — if n == 0 with fact(-1) recurses forever → RecursionError. Prefer n <= 1.
• Not shrinking the input — calling f(n) from f(n) is an infinite loop with extra memory.
• Slicing every call — nums[1:] copies the list, turning an O(n) recursion into O(n²) time and space.
• Deep linear recursion in Python — 10,000-node linked list = crash. Python has no tail-call optimisation; use a loop.
• Forgetting to return the recursive result — fact(n - 1) without return gives None at the top.
• Calling the same subproblem twice — power(x, n//2) * power(x, n//2) is O(n), not O(log n). Store it once.

Words to know

In two minutes

• A recursive function handles one level and calls itself on a smaller input; a base case stops it.
• Every call that is still waiting lives on the call stack, so space is O(depth) — fact(n) uses O(n) stack.
• Time = (number of calls) × (work per call). Draw the recursion tree and count the nodes.
• Naive fib(n) branches twice per call: about O(2ⁿ) time (precisely ~1.618ⁿ) but only O(n) space, because only one root-to-leaf path is on the stack at once.
• Caching results (memoisation) collapses fib to O(n) time and O(n) space — that is the doorway to dynamic programming.
• Python has no tail-call optimisation and stops at ~1,000 frames; deep linear recursion should become a loop.
• Use recursion when the data is nested (trees, folders, JSON, divide-and-conquer); use a loop when it is a flat sequence.

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.