Tail Call

In computer science, a tail call is a subroutine call that happens inside another procedure as its final action; it may produce a return value which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If any call that a subroutine performs, such that it might eventually lead to this same subroutine being called again down the call chain, is in tail position, such a subroutine is said to be tail-recursive. This is a special case of recursion.

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination, or tail call optimization.

Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops. In such cases, it is not correct (though it may be customary) to refer to it as an optimization.

Read more about Tail Call:  Description, Syntactic Form, Example Programs, Tail Recursion Modulo Cons, History, Implementation Methods

Other articles related to "tail call, tail, tail calls, calls, call":

Tail Call - Implementation Methods - Through Trampolining
... compilers use C as an intermediate target code, the problem comes down to coding tail recursion in C without growing the stack, even if the back-end compiler does not optimize tail calls ... a device known as a trampoline, a piece of code that repeatedly calls functions ... When a function has to call another, instead of calling it directly it returns the address of the function to be called, the arguments to be used, and so on, to the trampoline ...
Scala (programming Language) - Features (with Reference To Java) - Functional Tendencies - Tail Recursion
... Functional programming languages commonly provide tail call optimization to allow for extensive use of recursion without stack overflow problems ... Limitations in Java bytecode complicate tail call optimization on the JVM ... In general, a function that calls itself with a tail call can be optimized, but mutually recursive functions cannot ...

Famous quotes containing the words call and/or tail:

    There is also a reasonable tolerance: reason tolerates the reasonable. It is, however, almost tautological to call this ‘tolerance’ any longer, as it becomes a matter of course.
    Friedrich Dürrenmatt (1921–1990)

    His friends he loved. His direst earthly foes—
    Cats—I believe he did but feign to hate.
    My hand will miss the insinuated nose,
    Mine eyes the tail that wagg’d contempt at Fate.
    Sir William Watson (1858–1935)