In computer science, a tail call is a subroutine call that happens inside another procedure and that produces 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 a subroutine performs a tail call to itself, it is called 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. 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 to refer to it as an optimization, even if it is customary practice.

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. For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables), and the newly called function will return its result directly to the ''original'' caller. 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 non-recursive function calls, this is usually an 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 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, many times. In fact, it often asymptotically reduces stack space requirements from linear, or O(n), to constant, or O(1). Tail call elimination is thus required by the standard definitions of some programming languages, such as Scheme, languages in the ML family, and Haskell. In the case of Scheme, the language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context. 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'. in the context of compilation of Prolog, seen as an explicitly set-once language. As the name suggests, it applies when the only operation left to perform is to prepend new element in front of a list returned by the recursive call, thus non-tail. Instead, have the recursive call append elements to the end of the list. The following Prolog fragment illustrates the concept: partition([], _, [], []). partition([X|Xs], Pivot, [X|Rest], Bigs) :- X @< Pivot, !, partition(Xs, Pivot, Rest, Bigs). partition([X|Xs], Pivot, Smalls, [X|Rest]) :- partition(Xs, Pivot, Smalls, Rest).

Thus, this optimization moves the ''cons'' operation into the recursive call by creating a list node first, and passing this node into the recursive call, to be filled by it, instead of waiting for it to return and prepending an element in front of it. For example, consider a function in C language that duplicates a linked list: list *duplicate(const list *input) { list *head; if (input != NULL) { head = malloc(sizeof *head); head->value = input->value; head->next = duplicate(input->next); } else { head = NULL; } return head; }

In this form the function is not tail-recursive, because control returns to the caller after the recursive call duplicates the rest of input list. Even though it actually allocates the head node prior to duplicating the rest, the caller still has to plug into the next field the result from the callee. So the function is ''almost'' tail-recursive, save for a "cons" action, that is, tail recursive ''modulo cons''. Warren's method gives the following purely tail-recursive implementation which passes the head node into the callee so that ''it'' would set its next field itself:

list *duplicate(const list *input) { list head; duplicate_aux(input, &head;); return head.next; }

void duplicate_aux(const list *input, list *end) { if (input != NULL) { end->next = malloc(sizeof *end); end->next->value = input->value; duplicate_aux(input->next, end->next); } else { end->next = NULL; } }

Note how the callee now appends to the end of the list, rather than have the caller prepend to the beginning. Characteristically for this technique, a parent frame is created here in the execution call stack, which calls (non-tail-recursively) into the tail-recursive callee which could reuse its call frame if the tail-call optimization were present in C, thus defining an iterative computation.

The properly tail-recursive implementation can be converted into explicitly iterative form: list *duplicate(const list *input) { list head, *end; for ( end = &head; input != NULL; input = input->next, end = end->next ) { end->next = malloc(sizeof *end); end->next->value = input->value; } end->next = NULL; return head.next; }

History

In a paper delivered to the ACM conference in Seattle in 1977, Guy L. Steele summarized the debate over the GOTO and structured programming, and observed that procedure calls in the tail position of a procedure can be best treated as a direct transfer of control to the called procedure, typically eliminating unnecessary stack manipulation operations. Since such "tail calls" are very common in Lisp, a language where procedure calls are ubiquitous, this form of optimization considerably reduces the cost of a procedure call compared to other implementations. Steele argued that poorly implemented procedure calls had led to an artificial perception that the GOTO was cheap compared to the procedure call. Steele further argued that "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", with the machine code stack manipulation instructions "considered an optimization (rather than vice versa!)". Steele cited evidence that well optimized numerical algorithms in Lisp could execute faster than code produced by then-available commercial Fortran compilers because the cost of a procedure call in Lisp was much lower. In Scheme, a Lisp dialect developed by Steele with Gerald Jay Sussman, tail call elimination is mandatory.

Implementation methods

Tail recursion is important to some high-level languages, especially functional and logic languages and members of the Lisp family. In these languages, tail recursion is the most commonly used way (and sometimes the only way available) of implementing iteration. The language specification of Scheme requires that tail calls are to be optimized so as not to grow the stack. Tail calls can also be used in Perl, with a variant of the "goto" statement that takes a function name: goto &NAME;

Various implementation methods are available.

In assembler

For compilers generating assembly directly, tail call elimination is easy: it suffices to replace a call opcode with a jump one, after fixing parameters on the stack. From a compiler's perspective, the first example above is initially translated into pseudo-assembly language: foo: call B call A ret

Tail call elimination replaces the last two lines with a single jump instruction: foo: call B jmp A

After subroutine A completes, it will then return directly to the return address of foo, omitting the unnecessary ret statement.

Typically, the subroutines being called need to be supplied with parameters. The generated code thus needs to make sure that the call frame for A is properly set up before jumping to the tail-called subroutine. For instance, on platforms where the call stack does not just contain the return address, but also the parameters for the subroutine, the compiler may need to emit instructions to adjust the call stack. On such a platform, consider the code: function foo(data1, data2) B(data1) return A(data2) where data1 and data2 are parameters. A compiler might translate to the following pseudo assembly code: foo: mov reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register. push reg ; put data1 on stack where B expects it call B ; B uses data1 pop ; remove data1 from stack mov reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register. push reg ; put data2 on stack where A expects it call A ; A uses data2 pop ; remove data2 from stack. ret A tail call optimizer could then change the code to: foo: mov reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register. push reg ; put data1 on stack where B expects it call B ; B uses data1 pop ; remove data1 from stack mov reg,[sp+data2] ; get a copy of data2 into a scratch register mov [sp+data1],reg ; put data2 where A expects it jmp A ; A uses data2 and returns immediately to caller. This changed code is more efficient both in terms of execution speed and use of stack space.

Through trampolining

However, since many Scheme compilers use C as an intermediate target code, the problem comes down to coding tail recursion in C without growing the stack. Many implementations achieve this by using a device known as a trampoline, a piece of code that repeatedly calls functions. All functions are entered via the trampoline. 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. This ensures that the C stack does not grow and iteration can continue indefinitely.

It is possible to implement trampolining using higher-order functions in languages that support them, such as Visual Basic .NET and C#.

Using a trampoline for all function calls is rather more expensive than the normal C function call, so at least one Scheme compiler, Chicken, uses a technique first described by Henry Baker from an unpublished suggestion by Andrew Appel, in which normal C calls are used but the stack size is checked before every call. When the stack reaches its maximum permitted size, objects on the stack are garbage-collected using the Cheney algorithm by moving all live data into a separate heap. Following this, the stack is unwound ("popped") and the program resumes from the state saved just before the garbage collection. Baker says "Appel's method avoids making a large number of small trampoline bounces by occasionally jumping off the Empire State Building." The garbage collection ensures that mutual tail recursion can continue indefinitely. However, this approach requires that no C function call ever returns, since there is no guarantee that its caller's stack frame still exists; therefore, it involves a much more dramatic internal rewriting of the program code: continuation-passing style.

See also

Course-of-values recursion

Recursion (computer science)

Inline expansion

Leaf subroutine

References

Category:Programming language implementation Category:Implementation of functional programming languages

Category:Subroutines Category:Control flow Category:Recursion Category:Scheme programming language

Category:Articles with example C code Category:Articles with example Scheme code

de:Endrekursion fr:Récursion terminale lt:Uodeginė rekursija nl:Staartrecursie ja:末尾再帰 pl:Rekurencja ogonowa ru:Хвостовая рекурсия fi:Häntärekursio sv:Svansrekursion tr:Kuyruk özyineleme uk:Хвостова рекурсія zh:尾部递归