Where does recursion collide?

In the theory of computation, recursion is the definition of a function in terms of its own values on smaller or earlier arguments, over a well-founded structure that guarantees the definition terminates. Kleene's 1936 account of general recursive functions built the computable functions from base functions closed under composition, primitive recursion, and minimisation, and his recursion theorem later showed that a program can be given access to its own index. As Soare's 1996 review stresses, the referent here is a class of functions and a schema of definition, an object of pure mathematics, not a running program's control flow, a grammatical rule, or a thought about a thought.[1][2]

Unit

A function defined by recursion over a well-founded domain

Recovery means

Not applicable

Measured by

Studied by proof: showing a schema defines a total function, or classifying its position in the arithmetical hierarchy

In programming, recursion is a control-flow technique in which a procedure invokes itself on a reduced instance of the problem, with a base case that stops the descent and a recursive case that makes progress toward it. Dijkstra's 1960 note on recursive programming showed how a stack of activation records lets each call keep its own local state, which is what makes divide-and-conquer and tree traversal express so naturally as self-calls. As Structure and Interpretation of Computer Programs makes clear, the referent is a runtime implementation and coding idiom, judged by whether it terminates and how much stack it consumes, and not the abstract function schema of the logician.[3][4]

Unit

A self-invoking procedure with a base case and a recursive case

Recovery means

Each return unwinds one stack frame, restoring the caller's local state as the recursion collapses back toward the base case

Measured by

Assessed by tracing the call stack, counting recursion depth, and analysing time and space complexity of the recursive calls

In syntax, recursion is the property that a constituent can contain another constituent of the same type, so that a clause sits inside a clause or a noun phrase inside a noun phrase, in principle without a fixed upper bound. Hauser, Chomsky, and Fitch argued in 2002 that this discrete infinity is the core computational feature of the human language faculty, the mechanism that lets finite means generate unbounded expressions. The referent is a structural property of grammars, and its universality became contested when Everett reported that Pirahã appears to lack clausal embedding, a claim that turned recursion into the centre of a debate over what all human languages share.[5][6]

Unit

A grammar's capacity to embed a category inside a category of the same type

Recovery means

Not applicable

Measured by

Diagnosed from the grammar by testing whether embedded clauses and phrases can be nested and iterated within a sentence

In cognitive science, recursion names the mind's capacity to embed one representation inside another, most visibly in recursive mindreading of the form "I think that she believes that he wants," where each mental state is nested within a further mental state. Kinderman, Dunbar, and Bentall measured these orders of intentionality in 1998, finding that people track several levels of embedded belief before accuracy breaks down. As Corballis develops at book length, the referent is a psychological ability to represent representations, plausibly shared with mental time travel and grammar, and it is a claim about cognition rather than a function schema, a call stack, or a syntactic rule.[7][8]

Unit

The number of mental states a person can embed within one another

Recovery means

Not applicable

Measured by

Probed with layered story tasks that ask people to reason about beliefs about beliefs, scoring the highest order of intentionality reliably handled