Recursion defines things in terms of themselves, and programmers love joking about it
In short: Search Google in English for recursion and it asks whether you meant recursion. In some editions of the classic C programming book, the index entry for recursion lists its own page. Behind the jokes lies a serious idea: define something using a smaller version of itself, plus a stopping point so the chain ends.
Every sound recursive definition needs two ingredients. A base case answers the simplest situation directly, and a recursive step reduces every other situation toward that base. Ancestry is a tidy example: your parents are your ancestors, and so is any ancestor of a parent. The Fibonacci numbers work the same way, each the sum of the two before it, anchored by fixing the first two values at 0 and 1. Leave out the anchor and the definition spirals forever.
Mathematics builds whole foundations this way. The Peano axioms, set out in the 19th century by Richard Dedekind and Giuseppe Peano, amount to saying that zero is a natural number and every natural number has a successor, which generates all of them. Factorials, fractals such as the Cantor set, and even the set of provable statements in a logical system can be defined recursively, and proofs about them use structural induction. In economics and engineering, dynamic programming rewrites multi-step planning problems recursively through the Bellman equation.
Humans find it hard to carry out recursion by hand, because keeping track of several half-finished copies of the same procedure demands careful bookkeeping, which is why recursive definitions rarely appear in everyday life. Language may be the exception. Noam Chomsky and others argue that recursion explains why there is no upper limit on how many grammatical sentences a language can form, or how long one can be. Daniel Everett challenged that universality using his claims about the Pirahã language, and many linguists have pushed back against him.
Programmers, meanwhile, keep the humour alive with recursive acronyms: GNU stands for GNU's Not Unix, and WINE for WINE Is Not an Emulator. The self-referencing index gag predates the C book, appearing in Lisp and software texts published around 1976.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Recursion
To cite this card, link to https://intellectplus.co.uk/app/science-recursion.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?