Recursion
Recursion is the technique, and the mathematical idea behind it, of defining something in terms of a smaller version of itself, so that a problem is solved by reducing it to simpler instances of the same problem until one reaches a case simple enough to answer directly. It is a general tool of mathematics and computer science, appearing in definitions, proofs, algorithms, grammars, and data structures, and it only became prominent in AI because symbolic programs had so many self-similar problems to solve.
Every correct recursive definition has two parts: a base case that is answered directly, and a recursive case that reduces the problem toward the base case. The factorial of a number n is defined as n times the factorial of n minus one, with the factorial of zero defined as one. To compute the factorial of four, the definition asks for four times the factorial of three, which asks for three times the factorial of two, and so on down to the base case, after which the answers multiply back up to twenty-four. The base case is what makes the chain stop, and the requirement that each step move closer to it is what guarantees termination. A definition missing either part is not recursion but an infinite regress.
Fibonacci numbers give the standard example of recursion that is correct but wasteful. Each Fibonacci number is the sum of the two before it, with the first two fixed as zero and one, which translates directly into a function that calls itself twice. The program is faithful to the definition and also slow, because the same subproblems are recomputed again and again: computing the fifth Fibonacci number, which is five, takes fifteen calls, and the number of calls grows exponentially with the input. Remembering earlier results, a technique called memoization, or building values upward from the base cases, removes the repetition. The example shows that a recursive formulation is a clear statement of the problem and that making it efficient is a separate step.
The theoretical history of recursion is tied to the foundations of computability, a thread running through Gödel, Church, and Turing. Kurt Gödel used primitive recursive functions in his 1931 incompleteness paper and, following a suggestion from Jacques Herbrand, defined general recursive functions in his 1934 lectures. Alonzo Church's lambda calculus of the 1930s offered a different formalism, in which recursion is obtained through functions applied to themselves, and in 1936 Church and Alan Turing independently reached negative answers to Hilbert's decision problem, with Turing's machine model soon shown equivalent in power to general recursive functions and lambda definability. That convergence is the evidence behind the Church-Turing thesis, which says that these formalisms capture what can be effectively computed. The word recursive in recursion theory thus names a theory of computable functions as well as a coding technique.
Recursion entered programming through the languages of symbolic AI. John McCarthy built Lisp in 1958 around recursive definitions and conditional expressions, and his 1960 paper presented recursive functions of symbolic expressions as the basis of computation, while Newell, Shaw, and Simon had already used recursive subroutines in the IPL language for the Logic Theorist. Lisp's data suit recursion naturally: a list is either empty, the base case, or a first element followed by a smaller list, so a function can handle one element and trust itself with the rest. Algol 60 then brought recursive procedures into the mainstream, and today recursion is routine in tree traversal, divide-and-conquer sorting such as Tony Hoare's quicksort of 1961, parsing, and game-tree search.
The practical pitfall is that each pending call consumes memory, so deep recursion can exhaust the call stack in what is called a stack overflow. A function missing its base case, or given an input requiring a million nested calls, will crash or raise an error rather than return, and some languages cap depth deliberately: Python's default recursion limit is about a thousand frames. Scheme took a different path by requiring implementations to treat a call in tail position as a jump, which lets a suitably written recursive function run in constant stack space like a loop. Mainstream languages generally do not guarantee this, so deep recursion often gets rewritten with an explicit stack or a loop.
Several misconceptions cloud the topic. Recursion is not inherently faster or more elegant than iteration, because it is sometimes less efficient, as the Fibonacci example shows; any recursive procedure can be rewritten iteratively, and sometimes the rewrite is the better engineering. It is also not a concept peculiar to AI or programming, as mathematical induction is its twin in proof, and the grammars of natural language and fractal geometry have the same self-embedding shape. The common student confusion of imagining the whole chain at once also misleads: the reliable way to write a recursive function is to assume the smaller case already works and handle only the step and the base.
Read recursion as definition by self-reference anchored in a base case: a single idea that links Gödel's and Church's theory of computable functions to the call stack in every program, powerful exactly because the base case stops it and dangerous exactly when it is missing.