Tail call

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a tail call is a <a href="/facts/Subroutine/9vFJrg0A">subroutine</a> call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursion</a>. Tail recursion (or tail-end recursion) is particularly useful, and is often easy to optimize in implementations. 
Tail calls can be implemented without adding a new <a href="/facts/Stack_frame/1sMt713v">stack frame</a> to the <a href="/facts/Call_stack/1sMt713v">call stack</a>. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to <a href="/facts/Exec_(system_call)/x9bn7lFr">overlay</a> for processes, but for function calls). The program can then <a href="/facts/Jump_(computer_science)/obBGrnor">jump</a> to the called subroutine. Producing such code instead of a standard call sequence is called tail-call elimination or tail-call optimization. Tail-call elimination allows procedure calls in tail position to be implemented as efficiently as <a href="/facts/Goto/kWdNKT2M">goto</a> statements, thus allowing efficient <a href="/facts/Structured_programming/zA8b8dP1">structured programming</a>. In the words of <a href="/facts/Guy_L._Steele/amHwRA1l">Guy L. Steele</a>, "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions."
Not all programming languages require tail-call elimination. However, in <a href="/facts/Functional_programming_language/cdxqPEIM">functional programming languages</a>, tail-call elimination is often guaranteed by the <a href="/facts/Programming_language_specification/XSTQ2W2s">language standard</a>, allowing tail recursion to use a similar amount of memory as an equivalent <a href="/facts/Loop_(computing)/2XTDfErC">loop</a>. The special case of tail-recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller.

Tail call open-in-new

Tail call