Recursion (computer science)
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.
Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages 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 as imperative languages based on control structures such as and.
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 and one or more recursive case. This structure mirrors the logic of mathematical induction, which is a proof technique where proving the base case 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, 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, while others require an additional parameter to provide a stopping criterion.
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 > 0
Here, each invocation of the function decreases the input n by 1. Thus, it ensures that the recursion eventually reaches the base case of 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.
Examples
There are several practical applications of recursion that follow the base case and recursive case structure. These are widely used to solve complex problems in computer science.- Tree traversals, such as depth-first search, use a recursive case to process each subtree, eventually stopping at leaf nodes.
- Merge sort is a sorting algorithm that recursively sorts and merges divided subarrays until each subarray consists of one element.
- Fibonacci sequence is defined by summing the two previous numbers in the sequence, stopping when n = 0 or n = 1.
- Binary search repeatedly divides the search interval in half until the target is found or the interval is empty.
Recursive data types
Inductively defined data
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively :The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any number of strings.
Another example of inductive definition is the natural numbers :
A natural number is either 1 or n+1, where n is a natural number.
Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages. Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:
|
|
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complicated arithmetic expressions such as
), with more than one product or sum operation in a single expression.Coinductively defined data and corecursion
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.A coinductive definition of infinite streams of strings, given informally, might look like this:
A stream of strings is an object s such that:
head is a string, and
tail is a stream of strings.
This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the accessor functions
head and tail—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.Corecursion is related to coinduction, and can be used to compute particular instances of infinite objects. As a programming technique, it is used most often in the context of lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large result, and a mechanism for taking a finite portion of that result. The problem of computing the first n prime numbers is one that can be solved with a corecursive program.
Types of recursion
Single recursion and multiple recursion
Recursion that contains only a single self-reference is known as ', while recursion that contains multiple self-references is known as '. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Multiple recursion can sometimes be converted to single recursion. For example, while computing the Fibonacci sequence naively entails multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, while tracking two successive values at each step – see corecursion: examples. A more sophisticated example involves using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.