Programmer's Wiki
Advertisement

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.

Code Examples[]

 integer function factorial ( integer n ) 
 {
    if( n <= 1 )
        return( 1 )
    else
        return( n * 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.childNodes[] ) {
        Node ret = findNode( n, key );
        if( ret != null ) {
            return ret;
        }
    }
    return null;
}

Considerations When Using Recursion[]

Recursion can usually be replaced by other forms of iteration such as the while loop. Indeed, this is usually advisable as recursion tends to cost more than other forms of iteration, since each function call adds to the call stack. Not only does this mean that recursion is often less optimized, but also usually more dangerous in terms of causing crashes, due to the potential for stack overflow.

However, recursion can still be useful. 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, and due to the way the are laid out - with individual nodes only accessible by traversing previous ones, unlike the random access nature of arrays - often mean that recursive traversal requires less clock cycles spent on memory allocation and deallocation.

Infinite Loops[]

Be careful to make sure that your function has an end state and that it is reachable. It is very easy to introduce an infinite loop when using recursion.

Examples of Recursion[]

Recursive Definitions[]

For example, in spoken language, a phrase is made up of a collection of individual words and smaller phrases. This is a recursive definition, because a phrase can consist of phrases.

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.


References[]

Godel, Escher, Bach: An Eternal Golden Braid

See Also[]

Iteration

External Links[]

Advertisement