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.

What you will learn

By the end of this article, you should be able to:

• identify the base case and recursive step;
• check that each call moves towards the base case;
• trace a small recursive function without losing track of the result; and
• decide when recursion is clearer than iteration.

The central 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.

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

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

A worked example

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.

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.

A common misconception

You do not need to hold the entire call stack in your head before you can understand a recursive function. That approach often makes recursion feel more mysterious than it is.

Instead, assume the recursive call correctly solves the smaller problem. Then check two things: the input really is smaller, and the current call combines the smaller result correctly. A short trace remains useful for testing that model, but it is evidence rather than the whole explanation.

Try it yourself

Write a recursive function sum_to(n) that returns the sum of the integers from 1 to a non-negative integer n. Before revealing the answer, state the base case and explain how the recursive call moves towards it.

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

Use it in practice

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.

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.

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.

Related reading

• Bellman–Ford algorithm shows how repeated local updates build a correct result across longer paths.
• Debugging as a teachable habit develops the small-input tracing habit used to inspect recursive calls.