Recursion

The formula

f(n) = g( n, f(smaller n) ),     f(base) = known value

The general shape: solve the problem by calling yourself on a strictly smaller input, and hand-solve the smallest input directly. No base case, no answer — just a stack overflow.

n! = n · (n−1)!,     0! = 1

Factorial, the canonical recursive definition. Five applications of the rule take you from 5! down to 0! = 1 and back up to 120.

T(n) = 2·T(n−1) + 1,     T(0) = 0     →     T(n) = 2ⁿ − 1

Tower of Hanoi: move n−1 disks aside, move the big one, move the n−1 back. Ten disks cost 1,023 moves; twenty cost 1,048,575. Recursion wrote the algorithm in three lines and the recurrence priced it.

T(n) = a·T(n/b) + (split/merge work)

The divide-and-conquer template. Merge sort is a = 2, b = 2: split the list, sort each half by the same method, merge. A million-element sort bottoms out after log₂(10⁶) ≈ 20 levels of splitting — that shallow depth is why divide-and-conquer wins.

recursion depth × bytes per stack frame ≤ available stack

The physical budget. Every unfinished call holds a frame — return address, arguments, locals — until its children finish. Recursion is never free; you pay in stack memory proportional to depth.

Where you meet it

Parsing a test-config or telemetry file on the bench. Any format that nests — JSON, XML, TDMS group trees, a command grammar with parenthesized expressions — gets parsed by functions that call themselves on each nested level. Recursive-descent parsing is the standard hand-written technique: one function per grammar rule, each rule calling the rules it contains.
Walking a directory of test data. The script that sweeps a test stand's archive — every folder, every subfolder, every run — is a recursive tree walk, whether you wrote the recursion yourself or os.walk hid it from you. Same structure for a CAD assembly tree, a fault tree, or a requirements hierarchy.
Divide-and-conquer numerics. Quicksort and merge sort in your data pipeline, binary search over a sorted calibration table, the FFT butterfly splitting a transform into two half-size transforms. A successive-approximation ADC is the same idea in silicon: halve the search interval every clock.
Review board, flight software. Coding standards for safety-critical work — NASA JPL's Power of Ten rules among them — ban recursion outright, because unbounded stack depth is unprovable memory use. If your embedded code recurses, expect the finding.

How it works

Two ingredients make a recursive routine correct: a base case the code can answer without another call, and a guarantee that every recursive call moves strictly closer to that base case. Miss either one and the routine never returns; in practice it dies when the call stack runs out. That is the number-one recursion bug, and it hides well — the routine works on every test file until someone hands it deeper nesting, or a symlink loop turns the directory "tree" into a cycle. Tree algorithms assume trees. Feed them a graph with a cycle and the recursion chases its tail; the fix is a visited set, which is you admitting the structure wasn't a tree.

The second failure mode is depth. Each pending call occupies a stack frame, so a recursion 100,000 levels deep needs 100,000 live frames. Python defaults to a 1,000-call recursion limit for exactly this reason; embedded targets with a few kilobytes of stack have far less patience. Rule of thumb: recursion is safe when depth grows like log n (balanced trees, binary search, merge sort) and suspect when depth grows like n (recursing down a list, or a quicksort that always picks the worst pivot). Any recursion converts mechanically to a loop plus an explicit stack you manage yourself — same algorithm, but now the memory use is visible and testable. Some compilers do this for you when the recursive call is the last operation in the function (tail-call elimination); C compilers only sometimes, Python never. Do not bet flight software on it.

The third trap is repeated work. Computing Fibonacci by the naive two-call recursion is correct and catastrophically slow: fib(30) returns 832,040 after 2,692,537 function calls, because the same subproblems get re-solved millions of times. The cure is memoization — cache each result the first time — which drops the count to 31 distinct subproblems. When a recursion's subproblems overlap, memoize or switch to a bottom-up table; when they don't overlap (merge sort's halves are disjoint), plain recursion is already efficient.

What recursion actually buys you is proof by structure. A recursive routine mirrors an induction argument: show the base case right, show each level right assuming the level below, and you've verified the whole thing. For inherently nested data, the recursive version is the one you can read in a design review and believe.

History

Mathematicians defined things recursively long before anyone called it that, but the technique got its legal standing in 1888, when Richard Dedekind's essay Was sind und was sollen die Zahlen? proved that a function defined by "value at zero, plus a rule for getting from n to n+1" exists and is unique — the recursion theorem, the license behind every recursive definition since ^[1]^[2]. Recursion as recreation arrived five years earlier: Édouard Lucas published the Tower of Hanoi puzzle in 1883 under the anagram pseudonym "Claus," and its 2ⁿ − 1 solution became the standard first recursive algorithm every programmer meets ^[3]^[4]. In the 1920s and 30s the logicians took over — Skolem building arithmetic on recursive definitions in 1923, Ackermann exhibiting a function in 1928 that outgrows every primitive recursive one, Gödel making the definitions precise in 1931 — and recursive functions became one of the formal answers to "what can be computed at all" ^[2].

Programming caught up in 1960, twice in one year. John McCarthy built LISP around recursive functions operating on nested symbolic expressions, published in his paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine" ^[5]^[6]. And ALGOL 60 admitted recursive procedures, which left implementers the practical problem of a procedure calling itself while its first invocation was still open. Edsger Dijkstra's 1960 paper "Recursive Programming" in Numerische Mathematik solved it with the run-time stack — pushing a fresh frame per call — the mechanism every mainstream language has used since ^[7]^[8]. When your debugger shows you a call stack, you are looking at Dijkstra's fix.

Related tools

/tools/adc-resolution — a successive-approximation ADC is binary search in hardware: the same halve-and-recurse pattern, one bit per clock
/tools/rc-filter — the discretized filter y[n] = (1−α)·y[n−1] + α·x[n] is a self-referential definition running in real time; IIR filters are literally called recursive filters
/tools/half-life-decay — each half-life applies the same rule to the previous result, the simplest recursion an engineer trusts daily

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →