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
Why use recursion? When should I use it in programming?
[edit] Pros and Cons
[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
