Understanding Recursion

post ·
algorithms|programming

Recursion is one of those ideas that feels like a magic trick until, quite suddenly, it feels obvious. A function that calls itself sounds like it should spin forever, like two mirrors facing each other. And yet, given one small promise, it not only terminates — it often expresses a problem more honestly than any loop could.

That promise is the whole game. Get it right and the function reads like a definition; get it wrong and you meet Python’s RecursionError before your coffee is cold.

To understand recursion, you must first understand recursion.

The joke is old, but it hides a real instruction: a recursive definition is allowed to refer to itself, as long as each reference is smaller than the last and there’s a smallest case that refers to nothing at all.

1. The two ingredients

Every recursive function is built from exactly two parts, and leaving either one out is the source of nearly every recursion bug:

  1. A base case — the smallest input, which you can answer outright without recursing.
  2. A recursive case — which does a little work, then defers the rest to a smaller version of the same problem.

Miss the base case and the descent never bottoms out. Fail to shrink the input in the recursive case and, again, it never bottoms out. Both mistakes look different in the editor and identical at runtime.

2. A first example: factorial

Factorial is the “hello world” of recursion because its mathematical definition is already recursive: n! = n × (n − 1)!, and 0! = 1. The code barely has to do anything but restate that.

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case, on a smaller n

Read the base case out loud: n <= 1 returns 1. That <= is a less-than-or-equal sign — two characters, exactly as Python parses them — not the single glyph ≤, which Python would reject.

What actually happens when you call factorial(4) is that the machine builds a tower of paused calls — the call stack — each waiting on the one beneath it:

  • factorial(4) waits for factorial(3)
  • factorial(3) waits for factorial(2)
  • factorial(2) waits for factorial(1)
  • factorial(1) hits the base case and returns 1

Then the tower collapses back upward, multiplying as it goes: 1 → 2 → 6 → 24. The stack is doing the remembering for you, which is exactly why forgetting the base case is fatal — the tower just keeps growing until Python enforces its default recursion limit and stops you.

3. When recursion betrays you: Fibonacci

The naive Fibonacci is the cautionary tale. It’s a perfectly faithful translation of the definition, and it is catastrophically slow.

def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

The problem is that each call spawns two more, and those branches recompute the same values over and over — fibonacci(30) evaluates fibonacci(10) thousands of times. The work grows exponentially. Elegance is not the same as efficiency, and recursion makes it easy to write something beautiful that will never finish.

4. Memoization: remembering what you’ve already computed

The fix isn’t to abandon recursion — it’s to stop the machine from doing the same work twice. Cache each result the first time you compute it, and the exponential tree collapses into a straight line. Python hands you this for free with functools.lru_cache:

from functools import lru_cache


@lru_cache(maxsize=None)   # cache every result; a repeated call returns instantly instead of recomputing
def fibonacci_memo(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

Same shape, same base cases — one decorator, and fibonacci_memo(300) returns before you can blink. The recursion was never the problem; the repetition was.

5. Tail recursion, and why Python won’t help you

In many languages you can rewrite a recursion so the recursive call is the very last thing that happens — a tail call — and the compiler will reuse a single stack frame instead of building a tower:

def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)

Here nothing waits on the result of the recursive call; the answer is carried along in acc. A language with tail-call optimization would run this in constant stack space. Python, deliberately, does not — Guido has explained why more than once: he values readable tracebacks over the optimization. So in Python, this is honest to write but still overflows on deep inputs. When you truly need depth, reach for a plain loop.

6. Mutual recursion

Recursion doesn’t require a function to call itself — only to eventually call back to itself. Two functions can lean on each other:

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)


def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

It’s a contrived way to check parity, but it’s the honest skeleton of how real parsers and interpreters are built — a grammar of rules that call one another until they reach a terminal.

7. When to reach for it

Recursion earns its keep when the data is recursive. If the structure defines itself in terms of smaller copies of itself, recursive code will usually be shorter and clearer than the iterative equivalent:

  • Trees — file systems, the DOM, syntax trees. A node is a value plus a list of subtrees, which is a recursive definition already.
  • Divide and conquer — merge sort, quicksort, binary search: split the problem in half, solve each half the same way.
  • Backtracking — mazes, Sudoku, generating permutations: try a step, recurse, and unwind when it fails.

For a flat list you’re walking once, a loop is plainer and cheaper — don’t reach for recursion to prove a point. But when the shape of the problem is a tree, the recursive solution isn’t just elegant. It’s the one that tells the truth about the data.