Recursion — when (and how) to use it

Day 22. Week four begins. We open with the topic that every CS-101 student claims to understand and most production developers misuse — recursion.

The definition is small. A recursive function is a function that calls itself. That's it. Strip away the formalism and you're left with two requirements every recursive function must have.

One — a base case. The simplest input where the function returns a direct answer without further recursion. Without a base case, the function calls itself forever and you get a stack overflow.

Two — a recursive case. The function reduces the input to a smaller version of the same problem and calls itself with that smaller input. The smaller call returns; you combine its result with whatever local work you needed.

The call stack does the bookkeeping. Each call gets its own stack frame with its own local variables. When a call returns, its frame is popped off the stack. The recursion depth equals the number of frames on the stack at peak.

When does recursion fit naturally?

When the problem can be described as 'solve a smaller version of the same problem'. Tree traversal — the answer for a tree is the answer for the left subtree, plus the answer for the right subtree, plus something at the root. Trivially recursive.

Divide-and-conquer algorithms — mergesort, quicksort, fast Fourier transform. Same recursive shape.

When does it NOT fit?

Iterative state machines, where you walk through stages with a fixed transition table. Use a loop.

Deep recursive structures with no memoisation, where exponential branching makes the runtime explode. Add memoisation (Day 27 DP) or convert to iteration.

The rule — recursion is a thinking tool. Use it to UNDERSTAND a problem. Convert to iteration when the production code needs to be deeper than Python's stack allows.

The classic example of recursion gone wrong is naive Fibonacci.

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

Looks innocent. It's catastrophic. Each call branches into two more calls. Depth n means 2^n leaf calls. fib(40) computes the answer in seconds; fib(50) takes minutes; fib(60) takes hours. Exponential.

The culprit — fib(38) gets computed billions of times across the recursion tree, by different parent paths. Each one wastes work. We're recomputing answers we already know.

The fix is one decorator.

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

lru_cache wraps the function. Each unique (n,) call caches its result. The next time fib(38) is called, it returns from cache in O(1). Each n from 0 to N is computed once. Total: O(n).

fib(1000) now returns instantly. fib(10000) still works (until you hit Python's recursion limit, which is a separate issue).

This is the gateway to dynamic programming. Memoised top-down recursion is exactly equivalent to bottom-up DP, just with the recursion handling the dependency order automatically.

The broader lesson — when recursion has overlapping subproblems (the same input gets computed multiple times by different paths), memoisation drops a Big-O class. When subproblems don't overlap (mergesort, where each call works on a unique sub-array), memoisation does nothing.

Know how to recognise overlap. Look at the recursion tree. If you'd see the same arguments at different nodes, there's overlap. Memoise. The runtime drops dramatically.

Recursion shines on trees. The structure of a tree IS recursive — each subtree is a smaller tree of the same shape. The traversals follow naturally.

Three classical traversal orders, three tiny functions.

Inorder — left subtree, root, right subtree. For binary search trees, inorder traversal yields values in sorted order.

Preorder — root, left subtree, right subtree. Used for cloning trees, expression printing, file-system listing.

Postorder — left subtree, right subtree, root. Used for evaluating expression trees, deleting trees (you delete children before the root), computing properties that depend on subtree results.

Look at the snippet. Three functions, three lines of body each (plus the base case for empty subtree).

Each function returns a list. The recursion combines child results — left subtree's list, then current node, then right subtree's list (for inorder), or whatever order. The base case for None returns an empty list. Combining via list concatenation gives the full traversal.

This is recursion at its cleanest. The shape of the code matches the shape of the data. There's almost no incidental complexity — no manual stacks, no while-loops, no state tracking.

For production code, you'd usually use generators (yield from) instead of materialising lists, to keep memory bounded. That's a small refactor — yield each value, yield from each subtree's recursion. Same shape, lazy.

For very deep trees, recursion hits Python's stack limit (default 1000). Convert to iterative with an explicit stack — same algorithm, different bookkeeping.

For balanced trees and interview-sized problems, the recursive form is correct, fast, and clear. Code three traversals once; you have the shape forever.

Python's default recursion limit is 1000. The exact number is fine for shallow trees and interview problems; it's a wall for production code that might recurse deep.

Symptoms — RecursionError: maximum recursion depth exceeded in comparison. Usually triggered by:

A deeply nested data structure. JSON with 2000 levels of nesting (uncommon but happens with auto-generated config).

A tree skewed to one side. A sorted-input BST is essentially a linked list and recurses to depth N.

A bug in your base case that causes infinite recursion (until the stack limit catches it).

Three fixes, in order of preference.

Fix one — increase the limit if you're confident the recursion is bounded. import sys; sys.setrecursionlimit(10_000). Each frame uses a few KB of stack space, so even 10000 is comfortable on modern machines (10000 * a few KB = a few tens of MB).

Fix two — convert to iterative with an explicit stack. Same algorithm, just maintain a list of 'work to do' instead of using the call stack. Tedious but rock solid; no stack limit.

Fix three — use yield-based generators with a manual stack. Combines lazy iteration with iterative bookkeeping. Best for tree traversals on large trees in production.

What NOT to do — disable the recursion limit entirely or set it to 1 million. Python doesn't optimise tail calls, so deep recursion always uses real stack space. At 1 million frames, you'd OOM long before the function finished.

For interview problems, recursion is fine. For production code on user-supplied data of unbounded depth, prefer iterative or hybrid solutions. Defensive coding pays off.

End of Day 22. Week four opens with recursion — the topic that scares freshmen, that beginners overuse, that experienced developers reach for thoughtfully.

What we covered.

Morning, the framing. A recursive function has two parts — base case and recursive case. The base case stops the recursion; the recursive case reduces the problem to a smaller version of itself. Use recursion when the problem has natural recursive structure (trees, divide-and-conquer); avoid it for state machines or anything iterative-shaped.

Midday, the gateway from naive recursion to dynamic programming — memoisation. @functools.lru_cache turns exponential recursion into linear by caching subproblem results. Naive Fib is O(2^n); memoised Fib is O(n). The decorator is one line. The speedup is enormous.

Afternoon, three tree traversals (inorder, preorder, postorder) in three lines each. Recursion at its cleanest — the shape of the code matches the shape of the data. Production refinements (generators, iterative versions for deep trees) are small refactors on the same skeleton.

Evening, the Python recursion limit (default 1000) and how to handle it. Increase the limit for confident-bounded recursion. Convert to iterative for unbounded production cases. Don't disable the limit entirely — Python doesn't optimise tail calls, so deep recursion always burns stack.

A broader theme. Recursion is a thinking tool. It often clarifies a problem (this is just a smaller version of itself). For production code, the thinking tool sometimes converts to a loop with an explicit stack — same algorithm, friendlier to limits.

Tomorrow, Day 23, binary search. Beyond 'find an element in a sorted array' — patterns for finding boundaries, searching the answer space, parametric search.

See you in the morning.