← Back to resources
Problem-solving patterns

Recursion, visualized

A function that solves a problem by calling itself on a smaller piece — trusting that the smaller piece will be solved — then combining the results. Here is the mental model, step by step.

THE RECIPE

Four moves, every time

Almost every recursive solution follows the same shape. If you can fill in these four blanks, you have written the function.

1

Break it down

Split the problem into one or more smaller versions of the same problem. The pieces must be strictly smaller, so they march toward the base case.

2

Call recursively — assume it works

Call the function on each smaller piece and trust it returns the correct answer. Don't trace it in your head; take the "leap of faith."

3

Combine the sub-solutions

Take the answers from the smaller calls and assemble them into the answer for the current, larger problem.

4

Base case — the stop sign

Add a terminating condition: the smallest input you can answer outright, with no further recursion. Without it, the function calls itself forever.

THE BIG PICTURE

Down to the base, back up to the answer

Recursion has two phases. On the way down the problem keeps splitting into smaller pieces until it hits the base case. On the way up the small answers combine back into the full solution.

BREAK DOWN ↓ COMBINE ↑ factorial(4) = 4 × factorial(3) factorial(3) = 3 × factorial(2) factorial(2) = 2 × factorial(1) factorial(1) = 1 BASE CASE — stop here returns 1 factorial(1) 2 × 1 = 2 factorial(2) 3 × 2 = 6 factorial(3) 4 × 6 = 24 factorial(4) — answer! turn around
Breaking down (descent) Base case Combining (ascent)

Computing factorial(4): each call waits on a smaller one until factorial(1) answers directly, then the results multiply back up.

IN CODE

The four moves, mapped to lines

Here is the same example in Python. Notice how each comment lines up with one of the four moves.

def factorial(n):
    # MOVE 4 — base case / terminating condition
    if n == 1:
        return 1

    # MOVE 1 — smaller subproblem: factorial(n - 1)
    # MOVE 2 — recursive call, assume it returns the right answer
    smaller = factorial(n - 1)

    # MOVE 3 — combine the sub-solution into this answer
    return n * smaller

The leap of faith. When you read factorial(n - 1), don't trace it. Assume it already returns the correct factorial of n − 1. Your only job is to combine that result correctly — and to make sure the base case exists so the chain ends.

DON'T FORGET

The terminating condition is non-negotiable

A base case answers the smallest input without recursing. Leave it out and every call spawns another call — the stack grows until the program crashes (a "stack overflow"). Two things must be true for recursion to terminate:

A

There is a base case

At least one input is handled directly with a plain answer and no recursive call.

B

Every call moves toward it

Each recursive call uses a strictly smaller / simpler input, so the base case is always eventually reached.

RECAP

One sentence to remember it by

Break the problem into a smaller version of itself, call the function on it and assume the answer comes back, combine that answer into yours — and add a base case so the smallest version stops the chain.