Recursion
Named by 25 essays across 9 fields — each of them below, with the objects they name alongside it.
Pascal's triangle, in two colours
Shade the odd numbers in Pascal's triangle and a fractal appears. Nothing was designed to produce it, and the same shape arrives independently from a completely different construction.
The rectangle that eats itself
Cut a square off a golden rectangle and what is left is a golden rectangle. That single property is the whole of the golden ratio, and it explains both what the number really does and most of what is wrongly claimed for it.
One sequence, counting everything
The number of ways to cut a polygon into triangles is 1, 2, 5, 14, 42. So is the number of ways to bracket a product, the number of binary trees, and the number of paths that never cross a diagonal. They are the same count, and the reason is one picture.
A diagram turned on its side
Write a partition as rows of dots, then read the columns instead. Every theorem in this essay is that one move, and the move proves things that no formula suggests.
A walk that changes one thing at a time
Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.
An ordinal as a growth rate
Index a family of functions by the ordinals, each one iterating the last, and the index becomes a measure of how fast a function grows. The point where the index leaves what arithmetic can prove is exactly where the Goodstein sequence became unprovable.
Every partition, hidden in a product
Multiply out one factor for each part size and the coefficient of q to the n is the number of partitions of n. Nothing is being approximated: the product is a bookkeeping device that does the counting by multiplying.
The terms that cancel almost everything
Multiply out the product of 1 − q, 1 − q², 1 − q³ and so on, and nearly every coefficient is zero. What survives is a single plus or minus one at 1, 2, 5, 7, 12, 15 — and the reason is a way of pairing partitions off so that each pair cancels.
Curvatures that stay whole
Four circles touching one another satisfy an equation in their curvatures. Read it as a quadratic and the second solution is the first subtracted from something — so a packing that starts with whole numbers stays whole forever.
One word, and four objects
A balanced string of brackets, a lattice path, a triangulated polygon and a binary tree are four different-looking things counted by the same numbers. They are not four things that happen to agree — each is a way of writing the others down, and the translation is mechanical.
The equation a sequence satisfies
Write the whole sequence as the coefficients of one series, and the recursion becomes an equation with a square in it. Solving the equation by the ordinary quadratic formula produces the closed form, the growth rate and the correction term, none of which the recursion offers.
The run that lands one place along
Add up a run of entries down one of Pascal's diagonals and the total is another entry of the triangle — one row further down and one place along. The same triangle holds four more sums of that kind, and each is a different question answered by the same additive rule.
Every entry counts the routes to it
Turn Pascal's triangle forty-five degrees and it becomes a grid of street corners, with each entry counting the ways of walking there. Identities between the entries then become statements about routes, and the statements are proved by cutting the routes in one place.
Every rational in one sequence
The tree lists every positive fraction once and needs a tree to do it. One recursion on the whole numbers lists them in a single row — and each term of it counts something nobody was asking about, which is why the enumeration works.
How many cuts a fair share costs
Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.
The few points that cut a flat graph
Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.
Fair bits from an unfair coin
Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.
The ball that is largest in five dimensions
A disc of radius one has area π, a ball of radius one volume 4π/3, and in each further dimension the unit ball grows — until five, where its volume is 5.264, after which it shrinks towards nothing. The recursion that shows it is the ring dissection of the disc, done one dimension at a time, and the shrinking is not the ball getting small: it is almost all of a high-dimensional cube lying outside the ball, and almost all of the ball lying in a thin rind at its surface.
![Raising the input's type, and what becomes computable. N[o]: 299 functions, 0 not extended polynomials; N[o → o]: 163 functions, 42 not extended polynomials; N[(o → o) → o]: 128 functions, 46 not extended polynomials; N[o → o → o]: 72 functions, 33 not extended polynomials.](/f/raising-the-input-s-type-and-what-becomes-computable-671114cd.svg)
One type up
A numeral is an iterator, and the formula it proves fixes what it may iterate. At the lowest type it can only repeat the successor, and every function it computes is a polynomial — no predecessor. Let the same numeral iterate a function on functions and 2ⁿ appears; let it iterate a function that takes a function and returns a value, and the predecessor appears at size 15; let it iterate a pair of values, and the predecessor, halving and parity all arrive at size 16. The trick is Kleene's, from 1932, and an exhaustive search finds it without being told.
One type for every use
In the simply typed calculus a numeral must be told in advance what kind of thing it will iterate, and with input and output of one type it computes only polynomials with tests. Let a single type stand for every type — a numeral is then a term of type ∀X. (X → X) → X → X, used at whatever type each occasion needs — and the same few symbols compute subtraction, exponentials and Ackermann's function, which grows faster than anything built from primitive recursion. Every run still finishes, and the proof that it does lies just beyond the reach of second-order arithmetic.
Counting the subgroups of a free group
The free group on two letters has one subgroup of index 1, three of index 2, thirteen of index 3, then 71, 461, 3,447 and nearly thirty-two million of index 10. Each is a covering of a figure-eight with a marked sheet, so counting them is counting pairs of permutations that join every sheet to every other. Marshall Hall did it in 1949 by sorting every pair by how far one sheet can travel, and the recursion that comes out says the count is almost exactly n times n factorial.
Running a computation backwards with little memory
The reverse sweep that gives a whole gradient for the price of a few evaluations needs the computation's intermediate states in reverse order, and storing them all can cost more memory than the machine has. Keep only a few and recompute the rest, and the cheapest schedule has an exact answer found by Andreas Griewank in 1992: with c stored states and no step run more than r times, the longest chain that can be reversed is the binomial coefficient C(c + r, c). Pascal's triangle is the table of what memory buys.
A sort that never looks at the answers
Most sorting decides its next comparison from the last one. A sorting network decides them all in advance: a fixed sequence of swaps-if-out-of-order, wired up before any number arrives. Whether such a thing sorts everything can be settled by trying 2ⁿ strings of noughts and ones instead of n! orderings. Nineteen comparators sort eight numbers, and proving that nothing shorter sorts eleven took decades and a satisfiability solver. Over neighbours only, one single test, the reversed row, decides the whole question.
The last place in the circle
Forty-one people stand in a circle and every third is removed. Which place is safe? Counting round by hand is not necessary: the survivor is a running sum on a dial that grows by one each step. With every second person it is n's binary digits rotated by one place, which is a tidier fact than anybody asked for. With every third the rule depends on repeatedly multiplying by three halves and rounding up, and the constant it reaches, 1.62227…, has no known closed form.
A line that fires all at once
A line of soldiers, each knowing only its two neighbours and able to hold just a few states, must all fire at the same instant on an order given to the one at the end. No soldier can count, or knows the length of the line. Yet a rule table of seventeen states does it, tested on every line up to 300, by sending one signal three times as fast as another and letting them meet in the middle. The fastest possible rules do it in 2n − 2 steps, with six states; whether five can is still unknown.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting two waysBijectionBinomial coefficientLower boundAlgebraic identityBinaryGenerating functionParityCatalan numbersLattice pathsPartitionPermutation