| Revision as of 19:13, 12 December 2001 view sourceTaw (talk | contribs)Extended confirmed users2,615 editsm format fix← Previous edit | Revision as of 22:45, 16 December 2001 view source Taw (talk | contribs)Extended confirmed users2,615 edits see also: Primitive recursive functionNext edit → | ||
| Line 1: | Line 1: | ||
| '''Recursion''' is the definition of a ], be it mathematical or computational, in terms of itself. The canonical example is | '''Recursion''' is the definition of a ], be it mathematical or computational, in terms of itself. The canonical example is | ||
| the following definition of the ] function: | the following definition of the ] function: | ||
| :0! = 1 | :0! = 1 | ||
| :''n''! = ''n'' * (''n''-1)! for any ] ''n''>0 | :''n''! = ''n'' * (''n''-1)! for any ] ''n''>0 | ||
| Therefore, given this definition, we work out 3! as follows: | Therefore, given this definition, we work out 3! as follows: | ||
| 3! = 3 * (3-1)! | 3! = 3 * (3-1)! | ||
| = 3 * 2! | = 3 * 2! | ||
| = 3 * 2 * (2-1)! | = 3 * 2 * (2-1)! | ||
| = 3 * 2 * 1! | = 3 * 2 * 1! | ||
| = 3 * 2 * 1 * (1 - 1)! | = 3 * 2 * 1 * (1 - 1)! | ||
| = 3 * 2 * 1 * 1 | = 3 * 2 * 1 * 1 | ||
| = 6 | = 6 | ||
| Another, perhaps simpler way to understand recursive programming: | Another, perhaps simpler way to understand recursive programming: | ||
| 1. Are we done yet? If so, return the results.<br> | 1. Are we done yet? If so, return the results.<br> | ||
| 2. Simplify the problem and send it to 1.<br> | 2. Simplify the problem and send it to 1.<br> | ||
| Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of ]. | Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of ]. | ||
| Indeed, some languages designed for ] provide recursion as the only means of repetition ''directly'' available to the programmer. | Indeed, some languages designed for ] provide recursion as the only means of repetition ''directly'' available to the programmer. | ||
| Such languages generally make ] as efficient as iteration, letting programmers express other repetition structures (such as ] <code>map</code> and <code>for</code>) in terms of recursion. | Such languages generally make ] as efficient as iteration, letting programmers express other repetition structures (such as ] <code>map</code> and <code>for</code>) in terms of recursion. | ||
| Recursion is deeply embedded in the ], with the theoretical equivalence of recursive functions and ] at the foundation of ideas about the universality of the modern computer. | Recursion is deeply embedded in the ], with the theoretical equivalence of recursive functions and ] at the foundation of ideas about the universality of the modern computer. | ||
| See also: | See also: | ||
| * ] | * ] | ||
| * ] | |||
| * ] | * ] | ||
Revision as of 22:45, 16 December 2001
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: