Recursion, or Mirrors Inside Mirrors

• #recursion
• #algorithms
• #python
• #beginners

Stand between two mirrors and you see yourself, inside yourself, inside yourself, fading into green-tinted infinity. That's recursion. The only difference is that good recursion knows when to stop, while your reflection in the barber shop does not.

The definition

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs two parts:

1. A base case: the smallest version, answered directly.
2. A recursive case: break the problem down and call yourself.

def factorial(n: int) -> int:
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case

Forget the base case and you get the barber-shop mirrors: the function calls itself forever, until Python stops you with RecursionError: maximum recursion depth exceeded. It's the language's way of saying "please step out of the mirror."

Where recursion feels natural

Recursion shines when the data itself is recursive, meaning a thing that contains smaller things of the same kind:

• folders inside folders
• comments with replies with replies
• HTML elements inside elements
• family trees

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

Try writing that with plain loops and a manual stack. You can, but the recursive version reads like the definition: "the size of a folder is the sum of the sizes of what's inside it."

The trap: doing the same work twice

The famous bad example is Fibonacci:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Beautiful. Also terribly slow, because fib(30) recalculates fib(28) and friends over and over. The fix is memoisation: remember answers you've already computed.

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

That one line turns exponential time into linear time. It's also the doorway to dynamic programming, which is just recursion with a good memory.

When not to recurse

Python doesn't optimise deep recursion, and the default limit is around 1,000 calls. For something like "walk a linked list of a million nodes," a loop is safer. Recursion is a tool for clarity, not a personality trait.

How to think recursively

Don't try to trace every call in your head. Instead, trust the function: assume total_size(child) already works for smaller folders, and ask only "how do I combine those answers?" It's a strange leap of faith, a bit like believing your reflection will stop eventually. It always does, as long as you remember the base case.