Recursion

A function that calls itself. The trick is in the structure: every recursive solution has exactly two pieces, a base case that stops the recursion and a recursive case that reduces the problem to a smaller version of itself.

The mental model

To compute the factorial of 5:

factorial(5) = 5 × factorial(4)
factorial(4) =     4 × factorial(3)
factorial(3) =         3 × factorial(2)
factorial(2) =             2 × factorial(1)
factorial(1) =                 1                ← base case

Each call defers the multiplication until the smaller case returns. When the base case (n <= 1) is reached, the chain unwinds: 1 → 2 → 6 → 24 → 120.

In code:

def factorial(n):
    if n <= 1:
        return 1            # base case — don't recurse further
    return n * factorial(n - 1)  # recursive case — reduce by 1

Why two ingredients

A function with no base case recurses forever and crashes (stack overflow / RecursionError). A function with no recursive case is just a function — recursion is doing nothing.

The proof that a recursive function works is induction:

1. The base case is correct (you can verify it directly).
2. Assuming the smaller case is correct, the recursive case combines the smaller result correctly.

If both hold, the function is correct for every input. This is the same logical structure as mathematical induction; recursion in code is the computational analog.

When recursion fits

Recursion shines when the data is recursive in shape:

• Trees — every node has children that are themselves trees.
• Linked lists — every node has a "rest of list" that is itself a list.
• Nested data (JSON, XML, file systems) — directories contain directories.
• Divide-and-conquer algorithms — merge sort, quicksort, binary search on a tree.
• Parsing — expressions contain sub-expressions.

The classic example: walking a tree.

def sum_tree(node):
    if node is None:
        return 0
    return node.value + sum_tree(node.left) + sum_tree(node.right)

This is shorter, clearer, and more obviously correct than the iterative version with an explicit stack.

When iteration is clearer

Recursion is overkill for flat sequences:

# DON'T write this recursively:
def sum_list(xs, i=0):
    if i == len(xs): return 0
    return xs[i] + sum_list(xs, i + 1)

# Just write a loop:
total = 0
for x in xs:
    total += x

The iterative version doesn't grow the stack, doesn't have a "wait, what's the base case" moment for the reader, and doesn't risk hitting the recursion limit. For linear scans, accumulators, and counting, iteration wins.

The rule of thumb: recursion when the problem decomposes into smaller versions of itself; iteration when the problem is "do this thing N times".

Stack depth

Each recursive call pushes a frame onto the call stack. The frame holds the local variables, the return address, and a bit of bookkeeping.

Language	Default stack depth limit
Python	1000 (sys.getrecursionlimit())
JavaScript (V8)	~10,000 (varies; runtime decides)
Go	up to GB — goroutine stacks grow dynamically
C / Rust	~1MB OS stack ≈ tens of thousands of frames

If your recursion can go deeper than ~1000 levels (a tree with depth >1000, a list with >1000 items processed recursively), you have to either:

1. Increase the limit — sys.setrecursionlimit(10000) in Python. Quick fix.
2. Convert to iteration with an explicit stack — robust fix.
3. Use tail-call optimization — language-dependent; see below.

Tail calls and TCO

A tail call is a recursive call that's the last thing the function does:

def fact(n, acc=1):
    if n <= 1:
        return acc
    return fact(n - 1, acc * n)    # tail call — nothing left to do after

In a tail-call-optimizing language, the runtime reuses the current stack frame for the tail call instead of pushing a new one. Stack depth stays constant; you can recurse a million times without blowing the stack.

The catch: JavaScript and Python don't do TCO in practice. The ECMAScript spec mandated it in ES6; Safari implemented it; V8 (Chrome, Node) and Spidermonkey (Firefox) did not. Python's BDFL famously refused to add it. The result: tail-recursive code in JS/Python still grows the stack.

Language	Does TCO?
Scheme	Yes (mandated by spec)
Erlang / Elixir	Yes
Haskell	Yes
Rust	Limited (compiler may, but it's not guaranteed)
OCaml	Yes
Java	No
Python	No
JavaScript (V8 / Spidermonkey)	No
Safari (JavaScriptCore)	Yes — but you're alone
Go	No (unbounded stacks instead)

If you're writing a tail-recursive algorithm in a non-TCO language, you'll need to refactor to iteration if depth becomes a concern.

Memoization — the speedup recursion almost always wants

A naive recursive Fibonacci:

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

fib(35)   # takes seconds — exponential calls

The same call tree visits fib(10) over a million times for fib(35). Memoize to fix it:

from functools import cache

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

fib(35)   # instant — each value computed once

@cache (or @lru_cache) wraps the function in a dict that records f(n) for each n seen. On repeat calls with the same args, return the cached result. The mental model: turn an exponential algorithm into a linear one with one decorator.

JavaScript doesn't have a built-in memoize decorator; lodash provides _.memoize, or you write a one-liner.

Mutual recursion

Two functions that call 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)

Same rules apply (base case, recursive case). Mutual recursion is rare in everyday code but appears in parsing — e.g. an expression-parsing function calls a term-parsing function which calls back into expression-parsing.

Common bugs

• Forgot the base case. RecursionError immediately. Add a base case.
• Recursive case doesn't reduce. factorial(n) calls factorial(n) instead of factorial(n-1). Infinite recursion. Make sure each call moves toward the base.
• Off-by-one in the base case. if n == 0 when you mean if n <= 1. The recursion goes one level too deep.
• Mutating shared state inside recursion. Sometimes intentional (e.g. building a result list), often a bug. Prefer returning values up the stack.
• Naive recursion that's exponential. Fibonacci, naive subset sum. Memoize.

Recursion vs explicit stack

Any recursion can be rewritten using an explicit stack data structure. Sometimes this is necessary (deep trees in non-TCO languages). The translation is mechanical:

# Recursive
def walk(node):
    if node is None: return
    print(node.value)
    walk(node.left)
    walk(node.right)

# Iterative with explicit stack
def walk(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None: continue
        print(node.value)
        stack.append(node.right)
        stack.append(node.left)

The iterative version uses heap memory (the stack list) instead of the call stack — often unbounded where the call stack is bounded.

What to internalise

• Every recursion needs a base case and a reducing recursive case.
• Recursion fits tree-shaped data and divide-and-conquer; iteration wins for flat sequences.
• Each call adds a stack frame. Real-world stacks are bounded.
• TCO is the dream; most languages don't do it. Don't write tail-recursive Python expecting constant stack.
• Memoize anywhere the same input could be computed twice.