Recursion defines things in terms of themselves, and programmers love joking about it
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.
Source: Recursion
