Anonymous user
Category:Recursion: Difference between revisions
Removed extra sentence and added an example of a non-tail-recursive function becoming tail-recursive
No edit summary |
(Removed extra sentence and added an example of a non-tail-recursive function becoming tail-recursive) |
||
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]] 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 recursion call is the last call in the function. Because tail recursive functions can easily and automatically be transformed into a normal [[:Category:Iteration|iterative]] functions, tail recursion is used in languages like Scheme or [[OCaml]] to optimize function calls, while still keeping the function definitions small and easy to read. The actual optimization transforms recursive calls into simple branches (or jumps) with logic to change the arguments for the next run through the function.
Line 19:
Time is saved because each function return takes a long time relative to a simple branch. This benefit is usually not noticed unless function calls are made that would result in large and/or complex call trees. For example, the time difference between iterative and recursive calls of <tt>fibonacci(2)</tt> would probably be minimal (if there is a difference at all), but the time difference for the call <tt>fibonacci(40)</tt> would probably be drastic.
Sometimes, tail-recursive functions are coded in a way that makes the function not tail-recursive. The example above could become tail recursive if it were transformed to look like this:
<pre>function F with arguments
if end condition is met
return end condition value
else
return F called with new set of arguments</pre>
Below is a list of examples of recursion in computing.
| |||