| Revision as of 16:18, 6 April 2002 view sourceAxelBoldt (talk | contribs)Administrators44,499 editsNo edit summary← Previous edit | Revision as of 11:43, 7 April 2002 view source Damian Yerrick (talk | contribs)Autopatrolled, Extended confirmed users, Pending changes reviewers15,082 editsm recursionNext edit → | ||
| Line 25: | Line 25: | ||
| 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 ]s at the foundation of ideas about the universality of the modern computer. | ||
| See also: | See also: | ||
| * ] | |||
| * ] | * ] | ||
| * ] | * ] | ||
Revision as of 11:43, 7 April 2002
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: