Tail recursion: Difference between revisions

Revision as of 18:44, 9 October 2010

Revision as of 18:47, 9 October 2010

Line 1:

{{merge|Tail call|discuss=Talk:Tail recursion#Should be merged with Tail call|date=July 2010}}

In [[computer science]], '''tail recursion''' (or '''tail-end recursion''') is a special case of [[Recursion_(computer_science)|recursion]] in which any last operation performed by the function is aall recursive call,calls theare [[tail call]], or returns a (usually simple) value without recursions.
Such recursions can easily be transformed to iterations. Replacing recursion with [[iteration]], manually or automatically, can drastically decrease the amount of [[Call stack|stack]] space used and improve efficiency. This technique of iterative calculation is commonly used with [[functional programming]] languages, where the [[declarative programming|declarative approach]] and explicit handling of [[state (computer science)|state]] promote the use of recursive functions that would otherwise rapidly fill the [[call stack]].

==Description==

When a function is called, the computer must "remember" the place it was called from, the ''[[return address]]'', so that it can return to that ___location with the result once the call is complete. Typically, this information is saved on the [[call stack]], a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. With tail recursion, there is no need to remember the place we are calling from—instead, we can leave the stack alone, and the newly called function will return its result directly to the ''original'' caller. Converting a call to a branch or jump in such a case is called a ''tail call optimization''. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that its result be immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed.

For normal, non-recursive function calls, this is usually a [[micro-optimization]] that saves little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions, however, the stack space and the number of returns saved can grow to be huge, since a function can call itself, directly or indirectly, a huge number of times. In fact, it often asymptotically reduces stack space requirements from linear, or [[Big-O notation|O]](n), to constant, or [[Big-O notation|O]](1).

If several functions are ''mutually recursive'', meaning they each call one another, and each call they make to one another in an execution sequence uses a tail call, then tail call optimization will give a ''properly tail recursive'' implementation that does not consume stack space. Proper tail recursion optimization is required by the standard definitions of some programming languages, such as [[Scheme (programming language)|Scheme]]<ref>http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11</ref><ref>http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3</ref>.

The notion of tail position in Scheme can be defined as follows:

#''The body of a lambda expression is in tail position.''

#''If'' (if ''E₀'' ''E₁'' ''E₂'') ''is in tail position, then both E₁ and E₂ are in tail position.''

==Examples==