recursion
Let an agent explain recursion, relay definitions, programming techniques, termination and stack concerns, type theory uses and linguistic debates from computer science, mathematics and linguistics sources with positions attributed, describe the named forms, and distinguish recursion from iteration, induction, self-similarity and circular definitions.
Research draft, second pass
A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.
written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify
Researched by: Claude
Purpose and description
Let an agent explain recursion, relay definitions, programming techniques, termination and stack concerns, type theory uses and linguistic debates from computer science, mathematics and linguistics sources with positions attributed, describe the named forms, and distinguish recursion from iteration, induction, self-similarity and circular definitions.
The process in which a function, structure or definition refers to itself, used in mathematics to define sequences and sets, in computer science where a function calls itself with base cases to stop, including tail recursion, which compilers can optimise into loops, and anonymous recursion through fixed-point combinators, in type theory in forms such as F-bounded quantification, and in linguistics, where recursivity lets phrases be nested inside phrases, a claim central to generative grammar whose universality is debated, as in discussions of the Piraha language; nesting and self-similarity in fractals are related ideas.
What it is for: Defining and computing things in terms of themselves.
It can be explain recursion across fields; relay programming techniques and pitfalls; describe named forms; distinguish related concepts.
Distinguishing features
Self-reference
Base cases
Call stack use
Cross-disciplinary
What it looks like
Not a physical object; seen in code, formulas, nested structures and fractals.
Physical character
key requirement: base case for termination note
Y combinator: fixed-point combinator for anonymous recursion note - Curry
Piraha recursion debate: from 2005 note - Everett, attributed
How it is recognised
Self-reference with a base case
Anonymous recursion, nesting, F-bounded quantification, tail recursion, linguistic recursivity
Iteration repeats with loops; induction is a proof method; self-similarity is geometric; circular definitions lack a base
Related models
is a kind of - in registry terms
is related to -
includes -
is contrasted with -
In practice
Families and kinds
direct and mutual recursion
tail recursion
structural recursion
anonymous recursion
recursive types and bounded quantification
recursion in syntax
Standards and regulation
No regulation; language standards specify tail call behaviour in some languages such as Scheme
Failure modes and hazards
Infinite recursion without base cases
Stack overflow
Overstating linguistic universality claims
Also called
Where this came from
wikidata · CC0 1.0
Drafted structure
Bundle to layer to finding to question, as the second pass will find it: 4 bundles · 8 layers · 8 findings · 16 questions.
Understand What recursion is.
Definition.
Definition
Definition.
Definition
Definition.
- What is recursion, and how does it differ from iteration, induction, self-similarity and circular definitions? definition
- Is the question about programming, mathematics, type theory or linguistics? boundary
Forms
Named forms.
Forms
Forms.
- What are anonymous recursion, nesting, F-bounded quantification, tail recursion and linguistic recursivity? definition
- Which entry fits the specific form? action
Computing Programming.
Sources.
Base cases
Base cases and termination.
Base cases
Base cases.
- How do base cases stop recursion, and what causes stack overflow? provenance
- Which references are standard? provenance
Tail calls
Tail call optimisation.
Tail calls
Tail calls.
- How do compilers turn tail recursion into loops, and which languages guarantee it? provenance
- Which sources are cited? provenance
Theory Mathematics and types.
Science.
Functions
Recursive functions.
Functions
Functions.
- How did recursive function theory shape computability? provenance
- Which entry fits computable function? action
Types
Recursive types.
Types
Types.
- What is F-bounded quantification in object-oriented type systems? provenance
- Which entry fits bounded quantification? action
Context Language.
Attribution.
Syntax
Recursion in syntax.
Syntax
Syntax.
- Why do generative linguists treat recursion as central to language? provenance
- Which entry fits generative grammar? action
Piraha debate
Piraha debate.
Piraha debate
Piraha debate.
- What did Everett and his critics argue about recursion in Piraha, with positions attributed? provenance
- Is the presentation neutral and attributed? boundary
What the second pass must settle
- Should linguistic recursion be a separate entry?
- How should computer science sources be linked?
- Should F-bounded quantification be moved to type theory entries?