| Revision as of 16:16, 6 April 2002 view source62.98.251.68 (talk)No edit summary← Previous edit | Revision as of 16:18, 6 April 2002 view source AxelBoldt (talk | contribs)Administrators44,501 editsNo edit summaryNext edit → | ||
| Line 7: | Line 7: | ||
| 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> | |||
| *To understand recursion, you must first understand ] | |||
| 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:18, 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:
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: