Recursion Patterns

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement." — Niklaus Wirth

Part I of this Volume taught you how recursion works — the call stack growing frame by frame, each call suspended until the one beneath it returns, the whole tower unwinding back to your first caller. That was the mechanics. This chapter is about something harder and more valuable: recursion as a way of thinking. Because the engineers who reach for recursion fluently — in interviews and in production — aren't tracing stack frames in their heads. They've learned to see a problem, spot the smaller version of itself hiding inside it, and trust that the smaller version is already solved. Master that leap and you've laid the foundation for the two techniques the rest of this Part is built on: backtracking and dynamic programming.

Core Concepts

The recursive leap of faith

Here is the mental move that separates people who "get" recursion from people who fight it. To solve a problem of size n, you assume — for free, without proof — that you already have a working solution for a smaller size. Then you only have to answer two questions:

• The base case: what's the smallest input, the one so trivial you can answer it outright?
• The combine step: given the answer to a smaller instance, how do you build the answer to this instance?

That's it. You do not trace the whole thing. You do not follow the recursion all the way down and back up in your head — that way lies madness. You define the base case, define the one step, and trust the machine to handle the rest. That trust is what people mean by the "recursive leap of faith," and it is a genuine skill you build by doing, not by understanding stack frames better.

To compute factorial(n), assume factorial(n - 1) already works. Then factorial(n) is just n * factorial(n - 1), and the smallest case is factorial(0) = 1. You never had to think about factorial(3) while writing this. You only thought about one step and the floor.

Shape 1 — Linear recursion (one call per level)

The simplest shape: each call makes at most one recursive call. The stack goes straight down and straight back up, like a single thread of dominoes. Factorial, summing a list, reversing a string — all linear.

Notice reverse is shaped like linear recursion — one call per level — yet it's O(n²), because each level does O(n) work slicing and concatenating. The shape of the recursion and its total cost are two different things. We'll make that precise in a moment.

Shape 2 — Branching recursion (two or more calls)

When a call makes two or more recursive calls, the work fans out into a tree instead of a single line. This is where recursion gets powerful — and where it can get catastrophically expensive.

Read that second number again. Computing fib(10) — a value you could work out on paper in seconds — took 177 function calls. Why? Because the two branches recompute the same subproblems over and over: fib(8) is calculated by both fib(9) and fib(10), fib(7) three times, and so on. The tree is riddled with duplicated work. fib(50) this way would make over 40 billion calls and hang your browser. Hold onto this pain — it is the exact motivation for memoization and dynamic programming later in this Part.

Branching isn't always wasteful, though. When the branches explore different data, it's the natural, efficient way to walk a structure:

Same branching shape as fib, wildly different cost — O(n), not O(2ⁿ) — because each node is visited exactly once. The lesson: branching is expensive only when the branches overlap.

Two ways to build the answer: combine-up vs pass-down

There are two fundamentally different ways to accumulate a result recursively, and the distinction will follow you all the way through backtracking and DP. Here is the same problem — summing a list — done both ways:

The difference is when the work happens. In sumUp, each frame has unfinished business — it must wait for the recursive call, then add. That's head recursion (work on the way back up). In sumDown, the answer is complete by the time you hit the base case; each frame does its work before recursing and then just forwards the call. That's tail recursion (work on the way down). Backtracking will lean heavily on the pass-down style — you carry the "path so far" as an accumulator — while divide-and-conquer and DP lean on combine-up.

Shape 3 — Mutual recursion (brief)

Recursion doesn't have to be a function calling itself — two functions can call each other, taking turns toward the base case. The classic toy example is parity without arithmetic:

You'll meet mutual recursion for real when parsing (a parseExpression that calls parseTerm that calls back into parseExpression), but the shape is the same: shrink the input each hop, and every path leads to a base case.

Recurrence relations — eyeballing the cost

You don't have to guess a recursive function's complexity. Write down its recurrence relation — a formula for its cost T(n) in terms of smaller T — then read off the answer. Three patterns cover most of what you'll see:

The fastest way to see it without algebra is the recursion tree: draw the calls as a tree, then ask two questions — how deep does it go? and how much work is on each level? Multiply them. Naive fib branches into two at every level and only shrinks n by one, so it's roughly 2ⁿ nodes — the tree is nearly full and enormous. sumList branches into one and shrinks by one, so it's a single line of n nodes — O(n). This is exactly the analysis muscle from Part I's "Analyzing Time Complexity," now applied to the call tree instead of loops.

Common Mistakes

• Missing or wrong base case → stack overflow. factorial(n) with only return n * factorial(n - 1) never stops; it recurses into negatives until the stack explodes with RangeError: Maximum call stack size exceeded. Every recursion needs a reachable floor.
• Not making progress toward the base case. A recursive call like f(n) inside f(n) (forgetting the - 1), or shrinking a copy while checking the original, loops forever even with a correct-looking base case. The argument must move strictly toward the base every call.
• Recomputing overlapping subproblems. The naive-fib trap: if two branches ask for the same value, you're paying for it twice (and their branches, and theirs...). Exponential blow-up hides here. If subproblems overlap, memoize.
• Mixing side effects and return values. Half the function pushes into a shared array while the other half returns values — now the "answer" lives in two places and you can't reason about either. Pick one: build by returning, or build by mutating a passed-in accumulator, consistently.
• Assuming JS optimises tail calls. Rewriting to tail form and expecting no stack growth. In V8 it still grows O(n); deep recursion still overflows.
• Confusing recursion shape with total cost. reverse looks linear but is O(n²) because of per-level slicing. Always account for the work done at each level, not just the number of levels.

Interview Corner

Chapter Summary

• Design recursion with the leap of faith: assume the smaller instance is solved, then define just the base case and the combine step — don't trace the whole stack.
• The three shapes: linear (one call/level), branching (two+ calls/level), and mutual (functions calling each other). Branching is cheap when subproblems don't overlap, catastrophic when they do.
• Head/combine-up recursion does work after the call returns; tail/pass-down recursion carries an accumulator and does work before. Both styles will recur throughout backtracking and DP.
• JavaScript (V8) does not optimise tail calls — tail-recursive code still uses O(n) stack and can overflow.
• Read complexity off the recurrence relation or the recursion tree: T(n)=T(n−1)+O(1)→O(n), T(n)=2T(n/2)+O(n)→O(n log n), T(n)=2T(n−1)→O(2ⁿ). Shape and total cost are separate — account for work per level.
• The Fibonacci trap — recomputing overlapping subproblems — is the exponential cliff that motivates memoization and dynamic programming.
• Classic bugs: missing/unreachable base case, no progress toward it, and inconsistently mixing returns with side effects.

Editorial reflection — recursion frightens beginners because they try to hold the whole unwinding stack in their heads at once, and no one can. The professional's secret is smaller and stranger than that: you deliberately look at one step and one floor, and then you let go — you trust a machine to remember the rest. Learning to stop tracing and start trusting is the real lesson here, and it is the same act of faith, scaled up, that lets you reason about backtracking's branching search and dynamic programming's overlapping subproblems. Get comfortable with the leap now; everything ahead is built on it.