Category:Recursion: Difference between revisions
m Added note about iteration |
m Put sentences in a more logical order, concisified |
||
Line 10:
More than one end condition is allowed. More than one recursion condition is allowed.
Many recursion problems can be solved with an iterative method, or using a [[Loop Structures|loop]] of some sort (usually recursion and iteration are contrasted in programming, even though recursion is a specific type of iteration). In some languages, the factorial example is best done with a loop.
Below is a list of examples of recursion in computing.
|
Revision as of 14:56, 6 February 2008
Recursion is the idea that a function can come to an answer by repeatedly calling itself with new arguments until a "base case" or "end condition" is met. One good example is a factorial function. The base case for factorial is "0!" (some people like to use 1 or 2, but for instructional purposes 0 is OK). When 5 is sent as an argument to a recursive factorial function, the function does not know the answer right away. All it knows is that 5! = 5 * 4!. So it calls itself to find out what 4! is. This process continues until it gets to 0!, which is 1. Now it has built up a train of answers: 5! = 5 * 4! = 5 * 4 * 3! etc. and it can find the final answer. Other common examples include tree traversal and the min/max algorithm.
A pseudocode function to demonstrate recursion would look something like this:
function F with arguments if end condition is not met return F called with new set of arguments else return end condition value
More than one end condition is allowed. More than one recursion condition is allowed.
Many recursion problems can be solved with an iterative method, or using a loop of some sort (usually recursion and iteration are contrasted in programming, even though recursion is a specific type of iteration). In some languages, the factorial example is best done with a loop. Some other languages, like Scheme, are designed to favor recursion over explicit looping, using tail-recursion optimization to convert recursive calls into loop structures. If loop structures are not available (or not allowed) in your language, recursion is a good way to go.
Below is a list of examples of recursion in computing.
Pages in category "Recursion"
The following 30 pages are in this category, out of 30 total.