ZERO / HERO
Russian dolls

Recursion

The analogy

To count nested dolls you open one and ask the same question of what is inside: "how many dolls in there?" Eventually you open a doll that is solid — that is the base case, and the answers add back up on the way out. A problem that contains a smaller copy of itself is a recursive problem.

Visualizer

Dolls inside dolls

step 1 / 11
bottom

count(doll) on a set of nested dolls. Each call will ask the same question of a smaller doll.stack depth 0

📖 In depth — the full reference

Recursion — everything worth knowing

  • Anatomy: BASE CASE (the smallest doll — answered directly, no recursion) + RECURSIVE CASE (shrink the problem, trust the smaller call). Missing or unreachable base case = infinite descent = stack overflow.
  • The leap of faith: assume factorial(n−1) already works and only check that your step (× n) is right. Verifying the whole chain in your head is how people get lost.
  • Every call pushes a frame (m0l7's vending machines) — so recursion costs O(depth) memory even when the maths is O(1).
  • Recursion ⇄ iteration: anything recursive can be rewritten with an explicit stack, and simple tail-shaped recursions collapse to plain loops. Use recursion when the PROBLEM is recursive: trees, divide and conquer, backtracking.
  • The naive-fibonacci trap: fib(n) calling fib(n−1) AND fib(n−2) re-solves the same subproblems exponentially — O(1.6ⁿ). Caching answers (memoization) collapses it to O(n) — that observation IS dynamic programming, Module 8.
  • Where you have already used it: merge sort and quicksort (halves), DFS (neighbours) — recursion was load-bearing three lessons before it got named.

Python specifics

import sys
print(sys.getrecursionlimit())     # 1000 — Python's guard rail
# Exceed it -> RecursionError (a clean exception, not a crash).
# CPython does NOT optimise tail calls — Guido chose readable tracebacks.

from functools import lru_cache
@lru_cache(maxsize=None)            # memoization in one line
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(500))                      # instant — and arbitrary precision
def count(doll):
    if doll.inner is None:
        return 1                 # base case
    return 1 + count(doll.inner)

import sys
sys.getrecursionlimit()   # 1000 by default
# every pending call costs a stack frame
Check yourself

What stops a recursion?

Practice — write it yourself

factorial(n) — recursively: the machine that presses its own button. Base case first (0! = 1), or the stack grows forever.

Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser