Tail recursion: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 19:33, 1 December 2008

Redirect to:

@@ Line 1: / Line 1: @@
+#REDIRECT [[:Category:Recursion]]
-[[Category:Encyclopedia]]'''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.
-The benefits of this optimization are primarily [[System stack|stack]] related. Transforming recursive functions into iterative functions can save memory and time.
-Memory is saved by reducing an entire call stack into one function call. This way, more complex calls can be evaluated without running out of memory.
-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.