Recursion
without mystery

Recursion makes beginners nervous for good reason. A function appears to call itself, the stack grows, and it is easy to lose track of what is happening.

The subject is not magic. Recursion is a way of defining a problem in terms of a smaller version of the same problem, with a clear stopping point. Once those two pieces are visible, many recursive programs become readable.

The idea

Informally:

1. Base case — the smallest problem you can answer directly.
2. Recursive step — reduce the problem, call the same function on the smaller version, and combine the result.

If the base case is correct and each recursive step moves strictly toward that base case, the computation terminates.

That is the whole contract. Everything else is notation.

Two parts

When reading or writing a recursive function, ask two questions:

If you cannot answer both, the function is not ready to implement.

Factorial

The classic introductory example is the factorial of a non-negative integer n, written n!:

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

The base case is 0!. The recursive step multiplies n by the factorial of a smaller value.

def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Trace factorial(4) by hand:

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1 * factorial(0)
= 4 * 3 * 2 * 1 * 1
= 24

Each call waits for a smaller call to finish. The base case factorial(0) stops the chain.

Reading a recursive function

Use this reading order:

1. Find the base case first. What input ends the recursion?
2. Check progress. Does every recursive call use a strictly smaller or simpler input?
3. Trust the recursive call. Assume the smaller problem is solved correctly, then verify the combining step.
4. Test small inputs. 0, 1, and one non-trivial case often expose missing base cases or wrong progress.

Step three is the habit that unlocks recursion. You do not need to unfold the entire stack in your head. You need to believe that factorial(n - 1) returns the right value, then check that multiplying by n is correct.

The same reading habit helps with graph algorithms such as Bellman–Ford, where repeated relaxation steps build a correct result from smaller subproblems on shorter paths.

When recursion fits

Recursion is a natural match when:

• the data structure is recursive (lists, trees);
• the definition of the problem is recursive (factorial, tree traversal);
• a brute-force loop would obscure the structure you are exploiting.

It is a weaker default when:

• a simple loop is clearer and equally correct;
• depth could grow large enough to risk stack overflow;
• tail-call optimisation is not available and performance matters at scale.

For teaching, recursion is still worth learning because it trains you to decompose problems — a skill that transfers to induction, proof, and dynamic programming.

Common mistakes

Watch for these patterns in pupil work:

• Missing base case — infinite recursion until stack overflow.
• Wrong base case — stops, but on the wrong answer.
• No progress — recursive call does not move toward the base case.
• Duplicated work — naive Fibonacci recomputes the same values repeatedly (a good lead-in to memoisation or iteration).

Debugging recursive code uses the same habits as any other program: reproduce a small failing input, trace the calls, and name what you expected at each step.

What to practise next

If recursion still feels opaque, practise with tiny functions before large ones:

• sum a list recursively;
• reverse a string;
• traverse a nested list;
• implement binary search on a sorted array.

In each case, write the base case in plain English before writing Python.

Recursion is not an excuse for unclear code. It is a compact way to express structure — when the structure is real.