Editing Tail call (section)

==Description==
When a function is called, the computer must "remember" the place it was called from, the ''[[Return address (computing)|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 list of return locations in the order that the call locations were reached. In addition, compiler allocates memory for local variables of the called function and pushes register content (if any and/or relevant) onto stack. Typically, it is done by allocating a stack frame including saved registers, space allocated for non-register local variables, return address and call parameters (unless they are passed in registers). For tail calls, there is no need to remember the caller or preserve content of registers – instead, tail-call elimination avoids allocation of new stack frames and makes only the minimum necessary changes to the existing stack frame before passing it on,<ref>{{cite web|url=https://cstheory.stackexchange.com/q/7540 |title=recursion - Stack memory usage for tail calls - Theoretical Computer Science |publisher=Cstheory.stackexchange.com |date=2011-07-29 |access-date=2013-03-21}}</ref> and the tail-called function will return directly to the ''original'' caller. This, however, leads to complete loss of the caller's stack frame, which is sometimes considered as a hindrance in debugging. The tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function is bypassed when the optimization is performed.

For non-recursive function calls, this is usually an [[Program optimization|optimization]] that saves only a little time and space, since there are not that many different functions available to call. When dealing with recursive or [[mutually recursive]] functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be very significant, since a function can call itself, directly or indirectly, creating a new call stack frame each time. Tail-call elimination often reduces asymptotic stack space requirements from linear, or [[Big-O notation|O]](n), to constant, or [[Big-O notation|O]](1). Tail-call elimination is thus required by the standard definitions of some programming languages, such as [[Scheme (programming language)|Scheme]],<ref name='SchemeProperTailRec'>{{cite web|url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11 |title=Revised^6 Report on the Algorithmic Language Scheme |publisher=R6rs.org |access-date=2013-03-21}}</ref><ref>{{cite web|url=http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3 |title=Revised^6 Report on the Algorithmic Language Scheme - Rationale |publisher=R6rs.org |access-date=2013-03-21}}</ref> and languages in the [[ML (programming language)|ML]] family among others. The Scheme language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context.<ref>{{cite web|url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.20 |title=Revised^6 Report on the Algorithmic Language Scheme |publisher=R6rs.org |access-date=2013-03-21}}</ref> Implementations allowing an unlimited number of tail calls to be active at the same moment, thanks to tail-call elimination, can also be called 'properly tail recursive'.<ref name='SchemeProperTailRec' />

Besides space and execution efficiency, tail-call elimination is important in the [[functional programming]] idiom known as [[continuation-passing style]] (CPS), which would otherwise quickly run out of stack space.