| Revision as of 15:43, 25 February 2002 view sourceConversion script (talk | contribs)10 editsm Automated conversion← Previous edit | Revision as of 16:16, 6 April 2002 view source 62.98.251.68 (talk)No edit summaryNext edit → | ||
| Line 17: | Line 17: | ||
| Another, perhaps simpler way to understand recursive programming: | Another, perhaps simpler way to understand recursive programming: | ||
| *To understand recursion, you must first understand ] | |||
| 1. Are we done yet? If so, return the results.<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 ]. | ||
Revision as of 16:16, 6 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:
- To understand recursion, you must first understand recursion
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: