> ## Documentation Index > Fetch the complete documentation index at: https://agentconcepts.io/llms.txt > Use this file to discover all available pages before exploring further. # recursion > A structure or process is defined in terms of smaller instances of itself, with a base case that terminates the regress; the whole is generated by repeatedly reducing to a simpler copy of the same form until the base case is reached. computer-science linguistics mathematics # Recursion ## Description Recursion is the pattern of defining a structure or process in terms of smaller instances of itself, anchored by a base case that stops the regress. A recursive definition has two parts that must both be present: a *self-similar rule* (the part is the same kind as the whole — a list is an element followed by a smaller list; a tree is a node whose children are trees) and a *base case* (the smallest instance, resolved directly, that does not recurse). Between them sits a *reduction step* that always maps toward something strictly smaller, so the descent provably terminates. The diagnostic question — *"is this thing defined as a smaller copy of itself, and is there a base case that bottoms out the descent?"* — distinguishes genuine recursion from mere nesting or repetition. The missing base case is the load-bearing failure: a self-referential definition with no terminating bottom is non-well-founded (infinite regress, stack overflow, circular definition). Recursion's power is that one finite self-similar rule plus one base case generates unbounded structure — the same finite-rule-yields-unbounded-form move that recurs from grammar to fractal geometry. ## Triggers **User-initiated:** User describes something defined in terms of itself, a divide-and-conquer decomposition into the same kind of subproblem, a self-similar / fractal structure, or a "teams of teams" / nested-of-the-same-thing organization. **Agent-initiated:** Agent notices a problem whose subproblems have the identical shape to the whole, or a structure built from smaller copies of itself. Candidate inference: "this is recursive — what's the base case, and does every step strictly reduce toward it?" **Situation-shape signals:** Self-similar structure at multiple scales; a problem that decomposes into the same problem on smaller input; a definition that mentions itself; a need for a terminating base case to avoid infinite regress. ## Exclusions * **Fixed-point** — [fixed-point](/concepts/fixed-point) is a self-mapping value; recursion is a self-similar generative definition. One is a stationary point, the other a generating rule. * **Reflection** — [reflection](/concepts/reflection) is self-critique of behavior (an agent evaluating its own output); recursion is structural self-reference with a base case. No evaluative loop. * **Frame-story / nesting** — [frame-story](/concepts/frame-story) nests possibly-different content; recursion nests a smaller instance of the *same form* and bottoms out at a base case. * **Motif / repetition** — [motif](/concepts/motif) repeats coordinate peers; recursion descends into a smaller copy of the whole. ## Structure Internal structure of recursion: a table of its component slots and the concepts that fill them. ## Relationships Relationship neighborhood of recursion: a graph of the concepts it connects to and the concepts it is a part of. * [composite](/concepts/composite) — the composite pattern (a tree whose parts share the whole's interface) is the canonical structural instance of a self-similar definition; recursion is the rule a composite embodies. * [fixed-point](/concepts/fixed-point) — self-similar-generation vs self-mapping-stasis; a recursion may converge to a fixed point but is not one. * [bootstrapping](/concepts/bootstrapping) — both build up from a seed by repeated rule-application; bootstrapping is staged causal escalation, recursion is self-similar descent to a base case. * [frame-story](/concepts/frame-story) — containment-with-different-rules vs same-form-reduction-to-a-bottom. ## Examples McCarthy's foundational paper defines computation over symbolic expressions using functions that refer to themselves on smaller inputs, terminating at atomic base cases. A function over a list is defined by what to do with the empty list (the base case) and how to handle one element plus the result of the *same* function applied to the rest (the self-similar rule). The whole computation unfolds by repeatedly reducing to a smaller instance of itself until an atom is reached. This is the form that underwrites Lisp and, through it, the standard treatment of recursive definition in computer science. **Inference**: Recursion's defining requirement is visible here in its purest form: a self-reference paired with a base case and a reduction toward it. Drop the base case and the definition is non-terminating; drop the self-reference and there is no recursion, only a table. The construction shows why "what is the base case?" is the first question to ask of any recursive definition — it is the only thing standing between a finite rule and an infinite regress. Hauser, Chomsky and Fitch argue that recursion is the core computational property of human language: a sentence can contain a clause, which can contain another clause, without principled limit ("the cat the dog chased ran"). A phrase is defined in terms of phrases of the same kind embedded within it, so a finite grammar generates an unbounded set of hierarchical structures. They controversially propose recursion as possibly the only component unique to the human language faculty in the narrow sense. **Inference**: Linguistic embedding is recursion in a domain with no computers and no mathematics: the same self-similar definition (a phrase may contain a phrase) yields unbounded structure from finite means. The cross-domain match is exact — the part is the same kind as the whole, and the generative power comes precisely from that self-similarity. That a structural primitive defined for computation reappears, unaltered, as the proposed signature of human language is strong evidence the shape is portable, not field-bound. Mandelbrot's fractals are geometric structures defined recursively by self-similarity: each part of the shape is a reduced-scale copy of the whole, generated by applying the same construction rule at ever-smaller scales. A coastline, magnified, reveals bays-within-bays of the same statistical form; the Koch curve is built by replacing each segment with a smaller copy of the same motif, indefinitely. The structure at any scale is a smaller instance of the structure at the scale above. **Inference**: Fractal geometry is recursion made spatial: the self-similar rule operates over scale rather than over a list or a clause, but the shape is identical — a structure defined as smaller copies of itself. The mathematical-but-non-computational, then linguistic, then computational instances together isolate recursion as a structural primitive independent of any single substrate: it is the same self-similar-definition-with-reduction wherever it appears, only the dimension of "smaller" changes.