Recursion
From Programmer's Wiki
Contents |
[edit] Introduction
The term Recursion describes processes or structures which are defined or described in terms of themselves.
In programming, a procedure or function is said to be recursive if it calls itself.
[edit] Code Examples
integer function factorial ( integer n )
{
if( n == 0 )
{
return( 1 )
}
else
{
return( factorial( n - 1 ) )
}
}
Another example is a binary search or searching data in a tree structure.
Node findNode( Node curNode, string key ) {
if( curNode.key == key ) {
return curNode;
}
foreach( Node n in curNode.nodes[] ) {
Node ret = findNode( n, key );
if( ret != null ) {
return ret;
}
}
return null;
}
[edit] Using Recursion
Recursion is often taught to students to make it easier to understand some data structures. The operations that are applied to linked lists and trees in particular are much easier if you understand recursion. Recursion tends to cost more than other forms of iteration as each function call creates it's own stack.
[edit] Examples of Recursion
[edit] Recursive Definitions
For example, in spoken language, a phrase is be made up of a collection of individual words and smaller phrases. This is a recursive definition, because a phrase can consist of phrases.
[edit] Recursive Algorithms
In mathematics, the factorial of a number, N, can be expressed as the product of N with the factorial of N-1, unless N = 0, in which case the factorial is 1.
[edit] References
Godel, Escher, Bach: An Eternal Golden Braid
