Recursion (computer science): Difference between revisions

Revision as of 18:53, 28 November 2006

Revision as of 00:07, 1 December 2006

Line 1:

'''Recursion in computer programming''' defines a function in terms of itself. One example application of recursion is in [[recursive descent parser|parsers]]s for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs, or other data can be defined, parsed, or produced by a finite computer program.

==Recursive algorithms==

A common method of simplification is to divide a problem into subproblems of the same type. As a [[computer programming]] technique, this is called [[divide and conquer algorithm|divide and conquer]], and it is key to the design of many important algorithms, as well as being a fundamental part of [[dynamic programming]].

Virtually all [[programming language]]s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a [[call stack]], although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a [[stack (data structure)|stack]].

Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without the use of [[iteration]] through use of [[Continuation|continuations]], in [[Continuation-passing style|continuation-passing style]],; and conversely any recursive function can be expressed in terms of [[iteration]].

To make a very literal example out of this: If an unknown word is seen in a book, the reader can make a note of the current page number and put the note on a stack (which is empty so far). The reader can then look the new word up and, while reading on the subject, may find yet another unknown word. The page number of this word is also written down and put on top of the stack. At some point an article is read that does not require any explanation. The reader then returns to the previous page number and continues reading from there. This is repeated, sequentially removing the topmost note from the stack. Finally, the reader returns to the original book. This is a recursive approach.

Some languages designed for [[logic programming]] and [[functional programming]] provide recursion as the only means of repetition directly available to the programmer. Such languages generally make [[tail recursion]] as efficient as iteration, letting programmers express other repetition structures (such as [[Scheme (programming language)|Scheme's]]'s <code>map</code> and <code>for</code>) in terms of recursion.

Recursion is deeply embedded in the [[theory of computation]], with the theoretical equivalence of [[mu-recursive function]]s and [[Turing machine]]s at the foundation of ideas about the universality of the modern computer.

==Recursive programming==

[[John McCarthy (computer scientist)|John McCarthy]]'s [[McCarthy 91 function|91 function]] is another example of a recursively defined function.

One basic form of recursive computer program is to define one or a few '''base cases''', and then define rules to break down other cases into the base case. This ''analytic'' method is a common design for parsers for computer languages; see [[Recursive descent parser]].

Another, similar form is generative, or ''synthetic'', recursion. In this scheme, the computer uses rules to assemble cases, and starts by selecting a base case. This scheme is often used when a computer must design something automatically, such as code, a machine part or some other data.

The [[Quicksort]] and [[Mergesort]] algorithms are also commonly done using recursion, which allows them to run in an average of O(n log n) time.

One common example (using the [[Pascal (programming language)|Pascal]] programming language, in this case) is the function used to calculate the [[factorial]] of an [[integer]]:

Many operations involving tree data structures also use recursion, as it is often quite difficult to iteratively traverse a tree of unknown length.

'''function''' Factorial(x: integer): integer;

In addition, some numerical methods for finding approximate solutions to mathematical equations use recursion. In [[Newton's method]], for example, an approximate root of a function is provided as initial input to the method. The calculated result (output) is then used as input to the method, with the process repeated until a sufficiently accurate value is obtained.

'''begin'''

'''if''' x <= 1 '''then'''

Factorial := 1

'''else'''

Factorial := x * Factorial(x-1);

'''end'''

Here is the same function coded without recursion. Notice that this iterative solution requires two temporary variables; in general, recursive formulations of algorithms are often considered "cleaner" or "more elegant" than iterative formulations.

==Recursive programming ==

One basic form of recursive computer program is to define one or a few base cases, and then define rules to break down other cases into the base case. This is analytic, and is the most common design for parsers for computer languages.

'''function''' Factorial(x: integer): integer;

Another, similar form is generative recursion. This is synthetic. In this scheme, the computer uses rules to assemble cases, and starts by selecting a base case. This scheme is often used when a computer must design something automatically, such as code, a machine part or some other data.

'''var''' i, temp: integer;

'''begin'''

temp := 1;

'''for''' i := 1 '''to''' x '''do'''

temp := temp * i

Factorial := temp

'''end'''

===Recursion versus iteration===

The commonly used example (using the [[Euphoria programming language]], in this case) is the function used to calculate the [[factorial]] of an [[integer]]:

In the "factorial" example the iterative implementation is likely to be slightly faster in practice than the recursive one. This result is typical, because iterative functions do not pay the "function-call overhead" as many times as recursive functions, and that overhead is relatively high in many languages. (Note that an even faster implementation for the factorial function on small integers is to use a [[lookup table]].)

There are other types of problems whose solutions are inherently recursive, because they need to keep track of prior state. One example is [[tree traversal]]; others include the [[Ackermann function]] and [[divide-and-conquer algorithm]]s such as [[Quicksort]]. All of these algorithms can be implemented iteratively with the help of a [[stack (data structure)|stack]], but the need for the stack arguably nullifies the advantages of the iterative solution.

'''function Factorial ( integer X )

if X < 0 then return "Invalid argument" end if

if X = 0 then return 1 end if

return Factorial(X-1) * X

end function'''

Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, the stack space available to a thread is often much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

Although the recursive factorial function is calculating the same value as the iterative function below, depending on language implementation, recursive function may consume additional memory for each call. I.e. factorial(20) may use ten times more memory than factorial(10). The [[Scheme programming language|Scheme]] language is especially efficient at recursion, but naive recursive implementations in earlier versions of [[C programming language|C]] were very notoriously wasteful. Nowadays, only the most performance-hungry software, such as video games, missile guidance systems and graphics card drivers, should worry about whether recursion will be slower than iterative <tt>for</tt> or <tt>while</tt> loops.

Recursive functions are often regarded as more elegant than alternative implementations and they are usually shorter and simpler. To highlight this, here is the above function coded in the same language but without recursion:

'''function Factorial ( integer X )

integer temp_result

if X < 0 then return "Invalid argument" end if

temp_result = 1

for i = 1 to X do

temp_result *= i

end for

return temp_result

end function'''

In this particular example the iterative implementation is slightly faster in practice than the recursive one. (Note that an even faster implementation for the ''Factorial'' function is that of using a [[lookup table]].) There are other types of problems that seem to have an inherently recursive solution, i.e. they need to keep track of prior state. One example is [[tree traversal]], which is possible to implement iteratively with the help of a [[Stack (data structure)|stack data structure]], but the need for the stack arguably defeats the purpose of the iterative solution. Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, thread stacks are often much smaller than memory available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

===Recursion vs. Iteration ===

While recursion can simplify the solution of a problem, often resulting in shorter, more easily understood source code, it is often less efficient, in terms of both time and space, than iterative solutions. There are some methods to convert recursive algorithm into an iterative algorithm using a loop and branching structure.

==Recursive functions==

<!-- {{main|recursive function}} -->

Functions whose domains can be recursively defined can be given recursive definitions patterned after the recursive definition of their ___domain.

Line 59 ⟶ 53:

the following definition of the [[factorial]] function <math>f(n)</math>:

<math> f (0n) = 1</math>

\begin{cases}

<math>f (n) = n * f (n-1)</math> for any natural number <math>n > 0</math>

1 & \mbox{if } n = 0 \\

n \times f(n-1) & \mbox{if } n > 0 \\

\end{cases}

</math>

Given this definition, also called a '''recurrence relation''', we work out <math>f(3)</math> as follows:

Line 89 ⟶ 88:

</math>

==Types of Tail-recursive functions==

Most of simple recursive functions can be classified in one of following types of recursive functions.

===Tail recursive function===

{{main|Tail recursion}}

Tail-recursive functions are functions ending in a recursive call. For example, the following [[C (programming language)|C]] function to locate a value in a [[linked list]] is tail-recursive, because the last thing it does is call itself:

A function executes a number of tests and then if a certain test is true returns a certain value. If all tests evaluated as false, the function calls it self recursively on reduced input value. In tail recursive functions, the return value of last function call is the return value of the whole recursion. The template in [[Common Lisp]] would be:

<!-- If someone can rewrite these C functions in Pascal or Common Lisp, please go ahead. -->

(DEFUN ''func'' (X)

(COND (''end-test-1'' ''end-value-1'')

(''end-test-2'' ''end-value-2'')

; ...

(''end-test-n'' ''end-value-n'')

(T (''func'' ''reduced-x''))))

====Double-Test Tail Recursion====

The most common variant of Tail recursive function is double-test tail recursion. This type of recursion first tests if the recursion reached the end (without finding the result), then tests if it found result and if neither if true, calls it self recursively. The template in [[Common Lisp]] would be:

struct node {

(DEFUN ''func'' (X)

int data;

(COND (''end-test-1'' ''end-value-1'')

struct node *next;

(''end-test-2'' ''end-value-2'')

};

(T (''func'' ''reduced-x''))))

struct node *find_value(struct node *head, int value)

{

if (head == NULL)

return NULL;

if (head->data == value)

return head;

return find_value(head->next, value);

}

On the other hand, the <code>Factorial</code> function used as an example in the previous section is ''not'' tail-recursive, because after it receives the result of the recursive call, it must multiply that result by <code>x</code> before returning to its caller. That kind of function is sometimes called ''augmenting recursive''.

====Single-Test Tail Recursion====

If we are sure that the function will find what it's looking for eventually, we can omit the first test and only test if the result has been found. The template in [[Common Lisp]] would be:

Notice that a single function may be both tail-recursive and augmenting recursive, such as this function to count the odd integers in a linked list:

(DEFUN ''func'' (X)

(COND (''end-test'' ''end-value'')

(T (''func'' ''reduced-x''))))

struct node *count_odds(struct node *head)

===Augmenting Recursion===

{

In augmenting recursion, the return value of one function call is augmented before returning it to the calling function. Therefore, the return value of a recursion is not the same as a return value of each function call. The template in [[Common Lisp]] would be:

if (head == NULL)

(DEFUN ''func'' (X)

return 0;

(COND (''end-test'' ''end-value'')

if (T (''aughead-fun''>data ''aug-val''% 2 == 1)

return count_odds(head) + 1; /* augmenting recursion */

(''func'' ''reduced-x'')))))

return count_odds(head); /* tail recursion */

==Terminology==

}

Base Case: a simple case (of a recursive problem) that can be solved directly without further recursion.

==See also==

*[[McCarthy 91 function]]

*[[Recursion]]

==ReferencesReference==

* [http://www.cs.cmu.edu/~dst/LispBook/ David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"]

[[Category:SoftwareArticles designwith patternsexample C code]]

[[Category:Articles with example EuphoriaPascal code]]

[[Category:Articles with example Common Lisp code]]