Recursion

A matryoshka doll opens and there is a smaller matryoshka inside. Open that one and there is a smaller one inside that. The shape repeats until you reach the tiny solid doll at the center that does not open. Recursion is a function that contains a smaller version of itself, all the way down to a base case that does not call anything. The function defines the problem in terms of the same problem, one size down.

The idea is older than computing. Alonzo Church wrote it down in the 1930s as lambda calculus, the math that proves any computation can be expressed by functions calling functions. In 1958 John McCarthy built a programming language called LISP at MIT that put recursion at the center — every loop in early LISP was actually a function calling itself. Python inherited the recursion side of LISP through Guido's earlier exposure to Scheme. There is one famous corner where Python breaks with the LISP tradition: it refuses to do tail-call optimization. Guido has written publicly that he kept the rule because optimized tail calls erase frames from the traceback, and a missing frame is a bug you cannot find. Python's stack is sacred. It is also limited — by default to about 1000 frames deep — and that limit will bite you in this lesson.

A recursive function needs two parts. The base case is the smallest input where the answer is obvious — the solid doll at the center. The recursive case is the rule that turns a bigger problem into a smaller one. Factorial is the canonical first example. The factorial of 4, written 4!, is 4 × 3 × 2 × 1 = 24. Written recursively: factorial(n) = n × factorial(n - 1), with base case factorial(0) = 1.

Open recursion.py. Write the function with a depth parameter that prints what is happening at each level so the dolls open and close in your terminal.

def factorial(n, depth=0):
    indent = "  " * depth
    print(f"{indent}factorial({n}) called")
    if n <= 1:
        print(f"{indent}factorial({n}) returns 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returns {result}")
    return result
 
factorial(4)

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

Read the trace top to bottom. Every "called" line indents one more space — the function is going deeper into the dolls. The base case factorial(1) returns immediately. Then every "returns" line indents back out — the dolls are closing in reverse order, each one finally able to do its multiplication once the inner answer arrives. The shape on the screen is the call stack, the actual data structure Python uses to remember which function is paused and waiting for which. Each indent level is one frame on the stack.

Fibonacci is the example that shows the dark side. The Fibonacci sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21 — each number is the sum of the two before it. The recursive definition writes itself: fib(n) = fib(n - 1) + fib(n - 2), with fib(0) = 0 and fib(1) = 1.

def fib(n, depth=0):
    indent = "  " * depth
    print(f"{indent}fib({n})")
    if n < 2:
        return n
    return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)
 
fib(5)

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)

Look at the tree. fib(2) shows up three times. fib(1) shows up five times. The function is doing the same little computations over and over because each branch has no idea another branch already solved it. For fib(5) that is a small annoyance. For fib(40) it is a billion calls. The next lesson, dynamic programming, is about caching these results. For now let it run on fib(35) and feel how slow naive recursion gets — about 30 seconds on a modern laptop for a problem a sensible loop solves in microseconds. The recursion is correct. It is also a trap.

The Towers of Hanoi is the example where recursion shines and a loop does not. The puzzle is a stack of n disks on peg A in size order, biggest on the bottom. You move all n to peg C with two rules: move only one disk at a time, and never put a bigger disk on a smaller one. Peg B is the workspace. The recursive insight: to move n disks from A to C using B, first move n-1 disks from A to B (using C as workspace), then move the bottom disk from A to C, then move the n-1 disks from B to C (using A as workspace). The base case is moving 1 disk, which is just a move.

def hanoi(n, source, target, helper, depth=0):
    indent = "  " * depth
    print(f"{indent}hanoi({n}, {source}->{target}, helper={helper})")
    if n == 1:
        print(f"{indent}move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, helper, target, depth + 1)
    print(f"{indent}move disk {n} from {source} to {target}")
    hanoi(n - 1, helper, target, source, depth + 1)
 
hanoi(3, "A", "C", "B")

hanoi(3, A->C, helper=B)
  hanoi(2, A->B, helper=C)
    hanoi(1, A->C, helper=B)
    move disk 1 from A to C
  move disk 2 from A to B
    hanoi(1, C->B, helper=A)
    move disk 1 from C to B
move disk 3 from A to C
  hanoi(2, B->C, helper=A)
    hanoi(1, B->A, helper=C)
    move disk 1 from B to A
  move disk 2 from B to C
    hanoi(1, A->C, helper=B)
    move disk 1 from A to C

For 3 disks the puzzle solves in 7 moves. For n disks it takes 2^n - 1 moves — exponential, the bad kind of growth from big-o. The 19th-century French legend that came packaged with the puzzle claimed monks were moving 64 golden disks and the world would end when they finished. 2^64 - 1 moves at one move per second is about 585 billion years. The recursion is short. The work it produces is enormous.

The Python stack has a limit. sys.setrecursionlimit(100_000) raises it, but the real limit is the C stack underneath, which segfaults around 10000 frames on most machines regardless of the Python setting. Some recursive functions can be rewritten as loops with an explicit stack to dodge this. Tree traversals and Hanoi are natural recursions and you leave them recursive. Linear chains like factorial(1_000_000) should be loops. The right shape comes from how the problem itself branches, not from a love of one style.

You can break a number problem into smaller versions of itself. The next move is to walk a graph the same way — but the structure is no longer a single line of dolls. It branches.