What Is a Tail Call?

In computer programming, a tail call is a specific situation within program source code in which a function, subroutine or procedure returns an expected value by calling another function instead of simply passing a variable holding the return value. The name itself denotes that the function called to calculate the value to be returned is at the end, or tail, of the function calling it to supply a return value. A tail call is of interest to some programmers because, with certain optimizations or compiler behaviors, no additional stack space is used to store code locations of the main function; the tail function instead is used to generate the return value reports directly back to the call point where the original function was invoked. The use of a tail call is particularly useful in situations in which recursion is employed, because the amount of stack space used to store the caller addresses in cases in which the recursive calls nest very deeply could quickly run out and stop program execution. Although using tail calls can help increase speed, memory usage and efficiency in a program, it also can lead to situations in which the source code is restructured to use the calls in a way that makes it difficult to debug and track, especially with cases of recursion.

The existence of a tail call is due in large part to how the call stack works within most computer programs and system architectures. The stack, which is like a stack of plates, is a first-in, last-out data structure. When a function, subroutine or procedure is called, the address from which the call is made, called a stack frame, is stored in the stack. This means a program that calls Function A, which then calls Function B, will have two stack frames, one for Function B and another beneath it for Function A. After Function B is finished executing, its stack frame is popped from the top of the stack and execution returns to Function A, which has its frame popped off the stack when it is done, finally returning program control to the point from which the first function originally was called.

When a tail call is used, the return statement in a function directly uses the return value of another function as the data to be sent to the calling code. In the above example, if Function A calls Function B directly with the return statement, then a tail call has been formed. Within the call stack, instead of having a stack frame for both functions A and B, Function B will receive the return address from Function A and Function A’s stack frame will be popped and disposed of, meaning Function B will pass its return value directly back to the location that called Function A without first having to pass control back to Function A. This increases the speed of function calls as well as helping to keep down the amount of information in the stack.

The properties of a tail call can make them a very attractive option for recursive functions. A recursive function is one that calls itself repeatedly to calculate a value, as can be the case when traversing a list data structure. No additional stack frames are created for the nested function calls, so very deep levels of recursion can be performed safely without the immediate threat of a stack overflow and possible program termination.