Category:Recursion: Difference between revisions
Content added Content deleted
(Added pseudocode) |
(Added more explanation with more links) |
||
Line 1: | Line 1: | ||
'''Recursion''' is the idea that a function can come to an answer by repeatedly |
'''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 no 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 answer. Other common examples include tree traversal and the [http://en.wikipedia.org/wiki/Minimax min/max algorithm]. |
||
A pseudocode |
A pseudocode function to demonstrate recursion would look something like this: |
||
function F with arguments |
function F with arguments |
||
Line 8: | Line 8: | ||
else |
else |
||
return end condition value |
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 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. |
|||
Below is a list of examples of recursion in computing. |
Below is a list of examples of recursion in computing. |