← all systems · see it in The System
Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself.
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Recursion |
| born at | around 1000 AD (implicit induction); 1665 explicit (Pascal); 1888 recursion theorem; 1960 in programming |
| born precision | century; contested |
| boundary | Inside: the practice of defining, proving and computing things in terms of smaller versions of themselves (recursive definitions, base cases and recursive steps, self-calling functions, the call stack that holds pending calls, recursive data types, induction) and the structure it works on (recursively defined sets and functions, recursive grammars). Outside: the hardware and memory it runs on, the languages and people that carry it, and the plants and animals whose nested forms are read as recursive. |
| nested level | A part of mathematics and computer science (a technique and a class of definitions); carried by programming languages, compilers and processors, by human language and thought, and modelled in living forms. |
| scale | social |
Measures (16) published science
| characteristic clock: one call per level (depth n for factorial(n)) | 1 call per level |
| characteristic clock: LISP reclamation (garbage collection) cycle | several seconds |
| characteristic clock: first explicit induction (Pascal 1665) to Dedekind's recursion theorem (1888) | 223 years (derived from two dates the sources give) |
| LISP initial free-storage list | approximately 15,000 registers |
| Ackermann A(4,2): decimal digits | 19,729 digits |
| short-circuiting the base case on a perfect binary tree | 1/2 fraction of calls saved in the worst case |
| crows: center-embedded responses on two-pair transfer trials | about 40% (crow 1: 43.9%; crow 2: 31.4%) of transfer trials |
| crows: center-embedded responses at three-pair depth | 42.5% and 43.8% of transfer trials |
| center-embedded transfer responses (Ferrigno 2020) | U.S. adults 224/240; Tsimane' 157/251; U.S. children 217/500; monkeys 47/180; chance ~8% responses |
| macaque training before ~60% correct on length-4 mirror sequences | 10,000 to 25,000 trials |
| Pirahã corpus | 1149 sentences, 6830 words, mean 5.9 words per sentence |
| orangutan alarm-call levels: combination, bout, series gaps | ≤0.2 s; 0.2-2 s; 2-20 s seconds |
| levels of nested self-embedded isochrony in Sumatran female alarm calls | 3 levels |
| birds' divergence from the primate lineage | more than 320 million years |
| words added that drop Transformers from near-perfect to below chance on nested dependencies | 3 words |
| Pushdown Layers: syntactic generalization sample efficiency | 3-5x more sample-efficient |
Open contentions (4) open contention
Where sources or readings disagree. Both stay on the map.
- C-413 Where do thoughts come from?
booked: No theory is proven, so the map lists the main ones side by side and doesn't pick one. It shows where thinking is handled in the brain, not where thoughts start.
the other reading: language-specific mechanisms; domain-general symbolic resources; independent visuospatial mechanisms (Martins 2026 lists all three as debated) - C-2924 When did recursion begin?
booked: The map keeps the competing readings; none is ruled.
the other reading: rung 12: recursion as a programming technique, practical from the late 1950s (LISP, ALGOL 60) on the stack from 1946; rung 0 as structure: recursive functions as mathematical structure (general recursive = Turing computable, C-557); earlier rungs as carriers: self-embedded call rhythms in orangutans, nested branching in plants - C-2925 Do all languages use recursion?
booked: The map keeps the competing readings; none is ruled.
the other reading: Everett: Pirahã lacks embedding and has an upper-bounded sentence length; Nevins et al.: in the Merge sense every sentence of more than two words is recursive, so Pirahã meets it; Futrell et al. 2016: no unambiguous recursive embedding in a 1149-sentence corpus; consistent with a regular grammar, though not the only analysis - C-2926 Is recursion uniquely human?
booked: The map keeps the competing readings; none is ruled.
the other reading: recursion is the unique and defining feature of human language (Hauser, Chomsky and Fitch 2002, as Futrell 2016 reports); crows produce center-embedded sequences on par with children (Liao 2022); macaques after extensive training, with uniqueness possibly in speed and strategy (Jiang 2018); monkeys with more exposure (Ferrigno 2020); orangutan calls carry third-order self-embedded isochrony, so recursion likely evolved gradually (De Gregorio 2025); monkeys' bracket performance may be ordinal and associative strategies, not recursion (critics cited by Liao 2022)
Partners and parts published science
Built from / builds (6)
- Base case
- Recursive step
- Call stack
- Sorting algorithm
- Competition between recursion and iteration for a program's control flow
- Competition for control of the call stack (stack-smashing malware against the running program)
Sits inside / holds (3)
- Language (human language)
- Mathematics (the field: the practice and the structures it studies)
- Computer science (the field: the practice and the computation it studies)
Trades with (valence) (19)
- Syntax: how a language combines words into phrases and sentences (constituency and dependency, word order, agreement, recursion), how speakers build and parse it, how children learn it, how it differs across languages, and the field that studies it via sys:acoustic-wave · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Human (Homo sapiens) via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Grammar (the structure of a language, as linguistics describes it) via sys:acoustic-wave · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Computer memory via sys:computer-memory · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature mixed
- Plant (kingdom Plantae) via sys:plant · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature even
- Large language model via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature mixed
- Mathematics (the field: the practice and the structures it studies) via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Carrion crow via sys:electromagnetic-field · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature even
- Algorithm (the practice of step-by-step procedures and the structure they compute) via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Central processing unit via sys:electromagnetic-field · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Programming language via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Orangutan (Pongo) via sys:acoustic-wave · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Computer security via sys:computer-memory · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature loss
- Compiler via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Data structure via sys:computer-memory · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Mathematical proof: the practice of showing that a statement follows from axioms and earlier theorems, how it is written, checked (by people and machines) and accepted, and the derivations it works on via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
- Sorting algorithm via sys:computer-memory · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature even
- Matrix (mathematics): the rectangular array of numbers and its algebra, determinants and eigenvalues, matrices as linear maps, their history, and their use in physics, graphics and machine learning; the practice and the structure both booked via sys:written-record · Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature gain
expressed by (11)
- Generation/Synthesis
- Recombination/Composition
- Templating / Standardization
- Encapsulation & Modularity (Abstraction)
- Internal Coordination/Regulation
- Uncertainty Reduction/Learning
- Trail-Marking / Externalized Memory (Stigmergy)
- Resource Denial/Attrition
- Quick Harm Avoidance
- Validation of Effectiveness
- Scheduled Build-and-Dismantle (On-Demand Structure)
floor filled by (19)
- Grammar (the structure of a language, as linguistics describes it)
- Syntax: how a language combines words into phrases and sentences (constituency and dependency, word order, agreement, recursion), how speakers build and parse it, how children learn it, how it differs across languages, and the field that studies it
- Human (Homo sapiens)
- Language (human language)
- Computer memory
- Plant (kingdom Plantae)
- Natural number (the structure)
- Computable function
- Programming language
- Working memory
- Function in programming (subroutine)
- Compiler
- Data structure
- Proof by mathematical induction
- Sorting algorithm
- Base case
- Call stack
- Merge (linguistics)
- Matrix (mathematics): the rectangular array of numbers and its algebra, determinants and eigenvalues, matrices as linear maps, their history, and their use in physics, graphics and machine learning; the practice and the structure both booked
represents (1)
Kinds (10)
- Proof by mathematical induction
- Direct (single and multiple) recursion
- Mutual (indirect) recursion
- Tail recursion
- Structural recursion
- Generative recursion
- Primitive recursive function
- Recursive grammar / recursion in language
- L-system (parallel rewriting)
- Finite subdivision rule
Notes published science
- Cauliflower is a recursion whose base case never fires: its meristems keep trying to become flowers, fail, and start over while keeping a 'memory' of the try, which stacks spirals inside spirals across many scales (src:azpeitia-2021-cauliflower).
- Crows, whose brains split from ours over 320 million years ago, learned to peck nested brackets like {[( )]} and did as well as preschool children and better than macaques (src:liao-2022-crows).
- Language models can be near-perfect on nested sentences and then drop below chance when just three words are added inside the nest; people, by comparison, rarely go past two levels of center embedding in speech at all (src:lakretz-2021, src:liao-2022-crows).
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
recursion as computer scientists and mathematicians describe it: a rule that refers to a smaller instance of itself, run by calling itself down to a base case while the pending instances are held, so that a finite statement reaches an unbounded set (reader's view)
- L1: Structures that hold smaller copies of themselves, and problems that split into smaller ones of the same kind: lists and trees, nested sentences, branching plants, the natural numbers.
- L2: The definition taken in: a recursive definition read, a program parsed, a sentence heard, a sequence of nested brackets seen.
- L3: The rule: one or more base cases and a recursive step that reduces every case toward them (a production rule rewriting a category to itself).
- L4: Self-application: the function calls itself on a smaller instance; the rule embeds an instance of its own kind (Merge re-applied to its output; a branch inside a branch).
- L5: Holding the nest: each pending instance kept (a frame on the call stack, a push-down list, working memory) until the inner one returns; depth limited by the stack bound and by human memory (most sentences two levels of center embedding).
- L6: What the finite rule reaches: an infinite set from a finite statement, a unique function (Dedekind 1888), every computable function (recursion-only languages are Turing complete), statements for every n proved by induction.
- L7: Use back on the world: parsers, divide-and-conquer algorithms (merge sort, quicksort), tree traversal, programming languages built on it (LISP, ALGOL 60), unbounded sentences, models of plant growth.
the boardroom (shared floors)
- L3: The rule: base case(s) plus a recursive step reducing toward them; in grammar a category rewritten to itself; in induction a base case and a step.
- L4: Self-application: the rule applied to a smaller instance of its own kind: a call, an embedded clause (Merge re-applied to its output), a branch in a branch.
- L5: Holding the nest: pending instances kept until the inner one closes (the call stack, a push-down store, working memory); depth bounded by the stack and by memory.
- L6: What the finite rule reaches: an unbounded set, a unique function, every computable function; termination and correctness proved by induction.
- L7: Use: parsers, divide and conquer, recursive data, functional languages, sentences, growth models.
the call stack in machine memory: frames pushed and popped as a recursive program runs
- L1: Memory reserved for the stack, often set at program start; its size depends on language, architecture, threads and available memory.
- L2: A stack frame (activation record) per invocation: return address, parameters, locals.
- L3: Push on call, pop on return (last in, first out); LISP's SAVE and UNSAVE on the public push-down list.
- L4: The bound: overflow when the stack pointer passes the stack bound; tail calls reuse the frame instead.
way in: Hearing: embedded speech and nested call rhythms
- L1: Sound: sentences with clauses inside clauses ('The mouse the cat chased ran'); great-ape calls in nested tempo.
- L2: Units grouped by level: pulses inside sub-pulses; calls into combinations, bouts and series (0.2 s, 2 s, 20 s gaps).
way in: Learned examples: machines that learn recursive behaviour from data
- L1: Examples: corpora with nested constructions; input-output pairs of structurally recursive functions.
- L2: Self-attention over tokens, with no explicit recursive state unless a stack tape is added.
- L3: What is learned: shortcut algorithms; near-perfect on short nested dependencies, below chance on long ones.
way in: Nature's nested forms as input: branching plants and curds
- L1: Branching forms in living things: one part branching into similar smaller parts; cauliflower curds with spirals nested over many scales.
- L2: Read as rewriting: Lindenmayer's L-systems take an axiom and rewrite every symbol in parallel by production rules.
way in: Sight: nested forms and sequences (brackets, hierarchies, Droste images)
- L1: Nested visual forms: paired brackets on a touchscreen; visual hierarchies; the Droste cocoa tin.
- L2: Seen pairs and positions: crows, monkeys, children and adults order novel brackets center-embedded above chance.
way in: Sight: the recursive definition or program read
- L1: Marks: the definition in symbols (Fib(n) = Fib(n−1) + Fib(n−2)) or code (def factorial(n): ... return n * factorial(n - 1)).
- L2: Reading: the reader must tell the procedure from its running; students often miss the base case.
way in: The input instance: the argument handed to the call (a number, a list, a tree)
- L1: Data of a recursive type in memory: a list is empty or an element and a list; a tree a node and subtrees.
- L2: The argument passed in the call and tested against the base case (the empty list; n = 0; a Null node).
way in: The self channel: values returned by the inner calls
- L1: A value returned by an inner call (the result of factorial(n - 1)).
- L2: Control returned to the caller's saved point: the return address popped off the stack.
- L3: The caller's frame restored with its locals and the returned value.
- L4: Combined with the pending work: the solution assembled from the solutions of the simpler versions.
way in: The stack's own state: how much stack space is left
- L1: Stack memory: a limited amount of address space, often fixed at program start.
- L2: The stack pointer, moved by each frame's allocation.
- L3: Depth counted against a limit: the interpreter's recursion limit (Python), the stack bound.
- L4: The bound checked: past it, overflow and crash (or an error raised first).
way in: The statement to prove for every n (induction's input)
- L1: A statement P(n) to be shown for infinitely many cases.
- L2: Split into a base case and an induction step from n = k to n = k + 1.
way in: Thought: the recursive rule held and run in a mind
- L1: A thought arriving: the problem seen as made of smaller ones of its kind (origin contested, C-413).
- L2: Symbolic resources: lexical retrieval and serial arithmetic interfere with building visual hierarchies; purely visual load does not.
way out: Overflow: the crash when the stack bound is passed
- L1: The program crashes (or Python raises an error first).
- L5: Depth past the bound.
way out: Return: the value handed back to the caller
- L1: The value written where the caller reads it.
- L2: The return address popped; control back to the point after the call.
- L5: The base case reached or the combination done.
way out: Speech and calls: nested sentences and call sequences produced
- L1: Produced as sound: sentences, or orangutan alarm calls with three nested levels of tempo.
- L7: A nested utterance chosen.
way out: The finished result out to the world: a sorted list, a parse tree, a drawn plant
- L1: Output written or drawn (an L-system string translated into geometry).
- L7: The top call returns; the program uses the result.
way out: Touching or pecking a nested sequence (the bracket task)
- L1: The screen touched or pecked; reward or error tone follows.
- L4: Each bracket chosen in center-embedded order.
Sources (25) published science
Recursion (computer science) (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Liao DA, Brecht KF, Johnston M, Nieder A (2022) Recursive sequence generation in crows. Science Advances 8: eabq3356. doi:10.1126/sciadv.abq3356 (CC BY) (behind its links)
Call stack (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Sorting algorithm (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Ackermann function (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Lakretz Y, Desbordes T, Hupkes D, Dehaene S (2021) Causal Transformers perform below chance on recursive nested constructions, unlike humans. arXiv:2110.07240 (behind its links)
Murty S, Sharma P, Andreas J, Manning CD (2023) Pushdown layers: encoding recursive structure in Transformer language models. arXiv:2310.19089 (behind its links)
Primitive recursive function (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Martins MD (2012) Distinctive signatures of recursion. Phil Trans R Soc B 367: 2055-2064. doi:10.1098/rstb.2012.0097 (behind its links)
L-system (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Stack overflow (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Python Software Foundation. sys: system-specific parameters and functions (Python 3 documentation), getrecursionlimit (behind its links)
Matrix (mathematics) (Wikipedia, via Wikimedia Enterprise) (behind its links)
Zhang SD, Tigges C, Biderman S, Raginsky M, Ringer T (2023) Can Transformers learn to solve problems recursively? arXiv:2305.14699 (behind its links)
Tail call (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)