# Recursion

*406*pages on

this wiki

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 Edit

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 Edit

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 Edit

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 Edit

#### Recursive Definitions Edit

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 Edit

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 Edit

Godel, Escher, Bach: An Eternal Golden Braid