Category:Recursion: Difference between revisions
m Spelling/grammar |
tail recursion |
||
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 (i.e. using a [[Loop Structures|loop]] of some sort). The factorial example is best done with a loop. If loop structures are not available (or not allowed), recursion is a good way to go. Many languages are designed to favor recursion over explicit looping, using ''tail-recursion optimization'' to convert recursive calls into loop structures. [[Scheme]] is a notable example.
Below is a list of examples of recursion in computing.
|
Revision as of 17:01, 28 January 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 (i.e. using a loop of some sort). The factorial example is best done with a loop. If loop structures are not available (or not allowed), recursion is a good way to go. Many languages are designed to favor recursion over explicit looping, using tail-recursion optimization to convert recursive calls into loop structures. Scheme is a notable example.
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.