Recursion | Research & Encyclopedia Articles

Recursion

When a computed function (or procedure) calls itself, it is called "recursive." If the call is via one or more other functions then this group of functions are collectively called "mutually recursive." If a function were to always call itself whenever it is called, then it would never terminate. Since each call of the function requires an activation frame in the computer's memory, it would soon use up all of the computer's resources and bring it to a complete halt as well. Therefore, a recursive function first performs some test on its arguments to check for a "base case"--a condition under which it can return a value without calling itself. When it is called with higher values, then it calls itself with a lower value, and so on, until a base case is reached and values can be returned to the higher-level calling routines.

The canonical example for a recursive function or computation is the factorial function, defined as the product of the first n natural numbers. The factorial of 0 and 1 are defined to be 1, and the factorial of any larger number is defined to be the product of that number and the factorial of its predecessor. Therefore, a factorial can be recursively computed. For example, let us compute the factorial of 4 in this way:

• The factorial of 4 is, by definition, 4 times the factorial of 3.
• The factorial of 4 therefore is, by extension, 4 times 3 times the factorial of 2.
• That in turn similarly is 4 times 3 times 2 times the factorial of 1.
• Since the factorial of 1 is already known to be 1, the computation need be carried no further, and it suffices to simply derive the answer, which is 24.

Recursion is in some ways analogous to mathematical induction, and a problem that can be solved recursively can also be solved inductively. The application of recursion is also often called tail recursion, because the recursion step where the original function is called with new, usually smaller parameters occurs near the end or the "tail" of the function definition, with previous parts accounting for base cases where the function can yield a value without invoking itself.

It is relatively simple to write program code for a recursive function. Many classes of problems, especially those that lend themselves to solutions by divide-and-conquer techniques, are natural candidates for application of recursion. The credit for realizing the importance of recursion goes to Professor John McCarthy (formerly of the Massachusetts Institute of Technology, now at Stanford University). McCarthy strongly advocated the use of recursion in the design of Algol60, a precursor of modern programming languages such as Pascal and C. Later on, he developed the language Lisp, which introduced recursive data structures, as well as recursive procedures and functions.

In considering the use of resources by recursive procedures, it is natural to use a mathematical construct known as a recurrence equation. A recurrence equation over the natural numbers defines the value of a mathematical function at a given integer in terms of the value of that very function for a smaller integer. As with induction or recursion, the base case has to be stated separately, and the recurrence only applies for input values larger than the base case. Recurrence equations are important in other areas of discrete mathematics as well, such as in forming discrete analogues of differential equations.

The concept of recursion plays a central role in computability theory as well. In considering the question of computability, i.e., just what mathematical functions that map the natural numbers to the natural numbers are computable, a special class of functions called primitive recursive functions are defined. The primitive recursive functions are just those that can be derived by composing the constant function, the successor function, and the projection functions. The work of the great 20th-century mathematician Stephen Kleene showed that a computable set is just one which can be expressed as the range of a primitive recursive function. Because of Kleene's work and influence, the branch of learning known as recursion theory was developed, and is now also known as computability theory.

Recursion theory is very closely tied to the work of Alan Turing and Kurt Gödel, and the Halting Problem on Turing machines, and the incompleteness theorems of Gödel are most commonly expressed in recursion-theoretic terms as set forth by Kleene. The Halting Problem, for instance, can be expressed by saying that there is a set of natural numbers that is recursively enumerable but not recursive. Therefore, the concept of recursion plays a central role in questions of undecidability also.