EVOPEDIA

← 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.

aliasesRecursion
born ataround 1000 AD (implicit induction); 1665 explicit (Pascal); 1888 recursion theorem; 1960 in programming
born precisioncentury; contested
boundaryInside: 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 levelA 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.
scalesocial

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) cycleseveral 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 listapproximately 15,000 registers
Ackermann A(4,2): decimal digits19,729 digits
short-circuiting the base case on a perfect binary tree1/2 fraction of calls saved in the worst case
crows: center-embedded responses on two-pair transfer trialsabout 40% (crow 1: 43.9%; crow 2: 31.4%) of transfer trials
crows: center-embedded responses at three-pair depth42.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 sequences10,000 to 25,000 trials
Pirahã corpus1149 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 calls3 levels
birds' divergence from the primate lineagemore than 320 million years
words added that drop Transformers from near-perfect to below chance on nested dependencies3 words
Pushdown Layers: syntactic generalization sample efficiency3-5x more sample-efficient

Open contentions (4) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (6)

Sits inside / holds (3)

Trades with (valence) (19)

expressed by (11)

floor filled by (19)

represents (1)

Kinds (10)

Notes published science

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)

  1. 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.
  2. L2: The definition taken in: a recursive definition read, a program parsed, a sentence heard, a sequence of nested brackets seen.
  3. 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).
  4. 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).
  5. 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).
  6. 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.
  7. 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)

  1. 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.
  2. 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.
  3. 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.
  4. L6: What the finite rule reaches: an unbounded set, a unique function, every computable function; termination and correctness proved by induction.
  5. 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

  1. L1: Memory reserved for the stack, often set at program start; its size depends on language, architecture, threads and available memory.
  2. L2: A stack frame (activation record) per invocation: return address, parameters, locals.
  3. L3: Push on call, pop on return (last in, first out); LISP's SAVE and UNSAVE on the public push-down list.
  4. 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

  1. L1: Sound: sentences with clauses inside clauses ('The mouse the cat chased ran'); great-ape calls in nested tempo.
  2. 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

  1. L1: Examples: corpora with nested constructions; input-output pairs of structurally recursive functions.
  2. L2: Self-attention over tokens, with no explicit recursive state unless a stack tape is added.
  3. 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

  1. L1: Branching forms in living things: one part branching into similar smaller parts; cauliflower curds with spirals nested over many scales.
  2. 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)

  1. L1: Nested visual forms: paired brackets on a touchscreen; visual hierarchies; the Droste cocoa tin.
  2. 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

  1. L1: Marks: the definition in symbols (Fib(n) = Fib(n−1) + Fib(n−2)) or code (def factorial(n): ... return n * factorial(n - 1)).
  2. 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)

  1. L1: Data of a recursive type in memory: a list is empty or an element and a list; a tree a node and subtrees.
  2. 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

  1. L1: A value returned by an inner call (the result of factorial(n - 1)).
  2. L2: Control returned to the caller's saved point: the return address popped off the stack.
  3. L3: The caller's frame restored with its locals and the returned value.
  4. 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

  1. L1: Stack memory: a limited amount of address space, often fixed at program start.
  2. L2: The stack pointer, moved by each frame's allocation.
  3. L3: Depth counted against a limit: the interpreter's recursion limit (Python), the stack bound.
  4. 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)

  1. L1: A statement P(n) to be shown for infinitely many cases.
  2. 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

  1. L1: A thought arriving: the problem seen as made of smaller ones of its kind (origin contested, C-413).
  2. 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

  1. L1: The program crashes (or Python raises an error first).
  2. L5: Depth past the bound.

way out: Return: the value handed back to the caller

  1. L1: The value written where the caller reads it.
  2. L2: The return address popped; control back to the point after the call.
  3. L5: The base case reached or the combination done.

way out: Speech and calls: nested sentences and call sequences produced

  1. L1: Produced as sound: sentences, or orangutan alarm calls with three nested levels of tempo.
  2. L7: A nested utterance chosen.

way out: The finished result out to the world: a sorted list, a parse tree, a drawn plant

  1. L1: Output written or drawn (an L-system string translated into geometry).
  2. L7: The top call returns; the program uses the result.

way out: Touching or pecking a nested sequence (the bracket task)

  1. L1: The screen touched or pecked; reward or error tone follows.
  2. L4: Each bracket chosen in center-embedded order.

Sources (25) published science

Recursion (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01)
Recursion (computer science) (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
McCarthy J (1960) Recursive functions of symbolic expressions and their computation by machine, Part I. Communications of the ACM 3(4): 184-195. doi:10.1145/367177.367199 (author's copy) (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)
Mathematical induction (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Ackermann function (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Ferrigno S, Cheyette SJ, Piantadosi ST, Cantlon JF (2020) Recursive sequence generation in monkeys, children, U.S. adults, and native Amazonians. Science Advances 6: eaaz1002. doi:10.1126/sciadv.aaz1002 (behind its links)
Jiang X, Long T, Cao W, Li J, Dehaene S, Wang L (2018) Production of supra-regular spatial sequences by macaque monkeys. Current Biology 28: 1851-1859. doi:10.1016/j.cub.2018.04.047 (behind its links)
Futrell R, Stearns L, Everett DL, Piantadosi ST, Gibson E (2016) A corpus investigation of syntactic embedding in Pirahã. PLoS ONE 11: e0145289. doi:10.1371/journal.pone.0145289 (CC BY) (behind its links)
De Gregorio C, Gamba M, Lameira AR (2025) Third-order self-embedded vocal motifs in wild orangutans, and the selective evolution of recursion. Ann NY Acad Sci 1549: 219-229. doi:10.1111/nyas.15373 (CC BY) (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)
Azpeitia E, Tichtinsky G, Le Masson M, et al. (2021) Cauliflower fractal forms arise from perturbations of floral gene networks. Science 373: 192-197. doi:10.1126/science.abg5999 (behind its links)
Recursive data type (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Matrix (mathematics) (Wikipedia, via Wikimedia Enterprise) (behind its links)
Martins MJD, Cook DJ, Villringer A, et al. (2026) Recursion beyond language: lexical and arithmetic interference in visual hierarchical embedding. Psychological Research. doi:10.1007/s00426-026-02252-2 (CC BY) (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)