Recursion is the practice of defining something in terms of itself. The Stanford Encyclopedia of Philosophy explains that recursive functions take their name from “the process of recursion by which the value of a function is defined by the application of the same function applied to smaller arguments.” The classic example is the factorial: its value is defined by multiplying the argument by the factorial of a smaller number, unwinding the definition until a base case is reached.
A recursive definition needs two parts: one or more base cases that can be answered directly, and a recursive case that reduces a problem to a smaller instance of the same problem. Without a base case the unwinding never stops. The same shape appears in data structures, where a list or tree is described as either empty or a node holding smaller copies of the same kind of structure.
Recursion entered mainstream programming through ALGOL 60. The Revised Report on ALGOL 60 notes that “since the syntactic definition of both variables and function designators contains expressions, the definition of expressions, and their constituents, is necessarily recursive,” and its procedures could call themselves. This made recursion a first-class tool in a practical language, not just a topic in mathematical logic.
Recursion is also fundamental to LISP, whose original paper was titled “Recursive Functions of Symbolic Expressions and Their Computation by Machine,” and to parsing, where grammars describe nested structure by referring to themselves. The cost of unbounded recursion is the stack overflow: each call consumes stack space, so a recursion that never reaches its base case exhausts memory and crashes.