Tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, either manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack.
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 stack, a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. But in this case, there is no need to remember the place we are calling from — instead, we can leave the stack alone, and the newly called function will return its result directly to the original caller. Converting a call to a branch or jump in such a case is called a tail call optimization.
For normal, non-recursive function calls, this is usually a micro-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, however, the stack space and the number of returns saved can grow to huge numbers, since a function can call itself, directly or indirectly, a huge number of times. In fact, it often asymptotically reduces stack space requirements from linear, or O(n), to constant, or O(1).
Tail recursion is important to some high-level languages, especially functional languages. In these languages, tail recursion is the most commonly used way (and sometimes the only way available) of implementing iteration. The language specifications of Scheme and Erlang require that tail-recursive operations are to be optimized so as not to grow the stack.
Reference: Wikipedia
Let's first observe a normal recursive definition:
factorial1(0) -> 1; factorial1(N) when N > 0 -> N * factorial1(N - 1).
Note that the last operation (the tail call) in the second clause of factorial1/1 is the multiplication (and not the recursive call itself). Thus, this definition is not tail recursive. The following figure shows the stack growth behavior of a call using this function:
This second snippet uses tail recursion: the tail call in the second clause of factorial2/2 is the recursive call:
factorial2(N) -> factorial2(N, 1). factorial2(0, Accum) -> Accum; factorial2(N, Accum) when N > 0 -> factorial2(N - 1, Accum * N).
In this case, the Erlang compiler is able to produce a tail call optimization, so when the function is called, the stack space required is constant:
