A concept · The Shape of Things · Computing
Recursion
A thing defined in terms of smaller copies of itself.
How big is a folder? Add up its files, and then there are the folders inside it, each of which has files and folders of its own. The size of a folder is its files plus the size of each folder inside it, and that sentence uses the thing it is defining. Follow it down. Eventually there is a folder with no folders inside, whose size is just its files. That answer passes back up, and the totals assemble themselves on the way. When is a definition that refers to itself a trick, and when is it the clearest description there is?
What Recursion means
Recursion is a technique in which a procedure solves a problem by calling itself on a smaller instance of the same problem, descending until it reaches a case simple enough to answer directly, then assembling the answers on the way back up. Two parts make it work: a step that always makes the problem smaller, and a base case that stops the descent. Owning this changes how we meet structures that contain copies of themselves. A family tree, a sentence inside a sentence, a branch that splits into branches: each becomes one short rule applied at every scale. Every suspended step is held in memory until the bottom is reached, so the elegance is paid for in space, and a descent with no bottom fills that space until the program fails.
Recursion examples: where it shows up
- At work: an organisation chart, a bill of materials and a project plan are each made of smaller things of the same kind, and one short procedure walks all three.
- With money: a holding company owns companies that own companies, and valuing the top one means valuing each one beneath it by the same rule.
- In the news: the sorting behind every search result splits a list in half, sorts each half the same way, and merges, down to single items that are already sorted.
Where it sits
Open to walk. See where Recursion sits on the sky →
Nearest on the sky
A filled dot marks a star that is already open to walk.
Consuming content is one thing.
Connecting Recursion to your mental models is understanding. Apply it to your world today.
The first one is on us. No signup, no card.