In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure) do not define any built-in looping constructs, and instead rely solely on recursion. It is proved in computability theory that these recursion-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as while and for. Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for certain problems, algorithmic or compiler-optimization techniques such as tail call optimization may improve computational performance over a naive recursive implementation.
History
The development of recursion in computer science grew out of mathematical logic and later became an essential part of programming language design. The early work done by Church, Gödel, Kleene, and Turing on recursive function and computability laid the groundwork that made recursion possible in programming languages. Recursion has been used by mathematicians for a long time, but it only became a practical tool for programming in the late 1950s and early 1960s. Key figures such as John McCarthy and the ALGOL 60 design committee contributed to introducing recursion into programming. John McCarthy took the first steps by creating the programming language LISP in 1960. In his paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, McCarthy showed that recursion could be core in a programming language that works with symbols by processing them step by step. In LISP, recursion could be used in functions using simple rules, and there was also a way to evaluate them in the language. This demonstrated that recursion was a practical way to write programs and that it also describes the process of computation. Therefore, LISP became one of the first programming languages to use recursion as a main feature, and later on also influenced other languages that followed. During that time, recursion was also added to ALGOL 60. The Report on the Algorithmic Language ALGOL 60, which was published in 1960, was the outcome of an international attempt at designing a standard language. Allowing procedures to call themselves was one of the new important features of the language. Before that, only loops were allowed to be used by programmers, so it was a significant change. Recursion allowed programmers to describe algorithms in a more natural and flexible way.
Structure of a recursive function The definition of a recursive function is typically divided into two parts: one or more base case(s) and one or more recursive case(s). This structure mirrors the logic of mathematical induction, which is a proof technique where proving the base case(s) and the inductive step ensures that a given theorem holds for all valid inputs.
Base case The base case specifies input values for which the function can provide a result directly, without any further recursion. These are typically the simplest or smallest possible inputs (which can be solved trivially), allowing a computation to terminate. Base cases are essential because they prevent infinite regress. In other words, they define a stopping condition that terminates the recursion. An example is computing the factorial of an integer n, which is the product of all integers from 0 to n. For this problem, the definition 0! = 1 is a base case. Without it, the recursion may continue indefinitely, leading to non-termination or even stack overflow errors in actual implementations. Designing a correct base case is crucial for both theoretical and practical reasons. Some problems have a natural base case (e.g., the empty list is a base case in some recursive list-processing functions), while others require an additional parameter to provide a stopping criterion (e.g., using a depth counter in recursive tree traversal). In recursive computer programming, omitting the base case or defining it incorrectly may result in unintended infinite recursion. In a study, researchers showed that many students struggle to identify appropriate base cases.
Recursive case The recursive case describes how to break down a problem into smaller sub-problems of the same form. Each recursive step transforms the input so that it approaches a base case, ensuring progress toward termination. If the reduction step fails to progress toward a base case, the algorithm can get trapped in an infinite loop. In the factorial example, the recursive case is defined as:
n ! = n ⋅ ( n − 1 ) ! , ∀ n > 0. {\displaystyle n!=n\cdot (n-1)!\,,\forall n>0.}
Here, each invocation of the function decreases the input n {\displaystyle n} by 1. Thus, it ensures that the recursion eventually reaches the base case of n = 0 {\displaystyle n=0} . The recursive case is analogous to the inductive step in a proof by induction: it assumes that the function works for a smaller instance and then extends this assumption to the current input. Recursive definitions and algorithms thus closely parallel inductive arguments in mathematics, and their correctness often relies on similar reasoning techniques.
… excerpt ends here. Continue reading the full article.
