Recursive function

A recursive function is a mathematical function defined by self-referential equations: a base case that terminates the recursion and a recursive case that defines the function's value at n in terms of its value at smaller arguments. The concept, formalized by Gödel, Herbrand, and Kleene in the 1930s, is the foundation of computability theory. Every effectively calculable function is recursive, and every recursive function is computable by a Turing machine. The recursive functions are not merely a programming convenience; they are the mathematical definition of what it means to compute. The Church-Turing thesis asserts that this equivalence is not accidental but definitive: recursion is computation.