Anonymous user
Category:Recursion: Difference between revisions
m
Some extra explanations, link
m (formatting) |
m (Some extra explanations, link) |
||
Line 1:
[[Category:Solutions by Programming Task]]'''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]] (for positive integers only). The base case for factorial is "0!" (some people like to use 1 or 2, but 0 is OK for instructional purposes). 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 [[wp:Minimax|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''
''//optional additional conditions which may or may not have direct answers''
'''else'''
'''return''' ''end condition value''
Line 12:
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 because of function call overhead. Some other languages, like [[Scheme]], are designed to favor recursion over explicit looping, using tail recursion optimization to convert recursive calls into loop structures.
'''Tail recursion''' is a specific type of recursion where the
The benefits of this optimization are primarily [[System stack|stack]] related. Transforming recursive functions into iterative functions can save memory and time.
Line 24:
'''if''' ''end condition is met''
'''return''' ''end condition value''
''//optional additional conditions which may or may not have direct answers''
'''else'''
'''return''' ''F called with new set of arguments''
| |||