Misplaced Pages

This is an old revision of this page, as edited by AxelBoldt (talk | contribs) at 16:18, 6 April 2002. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Recursion is the definition of a function, be it mathematical or computational, in terms of itself. The canonical example is the following definition of the factorial function:

0! = 1

n! = n * (n-1)!   for any natural number n>0

Therefore, given this definition, we work out 3! as follows:

3! = 3 * (3-1)!
   = 3 * 2!
   = 3 * 2 * (2-1)!
   = 3 * 2 * 1! 
   = 3 * 2 * 1 * (1 - 1)!
   = 3 * 2 * 1 * 1
   = 6

Another, perhaps simpler way to understand recursive programming:

1. Are we done yet? If so, return the results.
2. Simplify the problem and send it to 1.

Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of iteration. Indeed, some languages designed for 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's map and for) in terms of recursion.

Recursion is deeply embedded in the theory of computation, with the theoretical equivalence of recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.

See also:

• Self-reference
• Primitive recursive function