Tail recursion is an idiom for writing certain kinds of recursive functions. It does not require any new language features, but many implementations of functional languages like Racket or ML do recognize and optimize the use of tail recursion. Tail-recursive functions often use the accumulator pattern to transform a natural recursive function into tail-recursive form.

To understand tail recursion and accumulators, consider these
functions for summing the elements of a list:

(define (sum1 xs)
  (if (null? xs)
      0
      (+ (car xs) (sum (cdr xs)))))

(define (sum2 xs)
  (define (sum-tail acc xs)
    (if (null? xs)
        acc
        (sum-tail (+ (car xs) acc) (cdr xs))))
  (sum-tail 0 xs))

Both functions compute the same results, but sum2 is more
complicated, using a local helper function that takes an extra
argument, called acc for “accumulator.” In the base case of
sum-tail we return acc and the value passed for the outermost
call is 0, the same value used in the base case of sum1.
This pattern is common: The base case in the non-accumulator style
becomes the initial accumulator and the base case in the accumulator
style just returns the accumulator.

Why might \verb|sum2| be preferred when it is clearly more
complicated? To answer, we need to understand a little bit about how
function calls are implemented. Conceptually, there is a
\emph{call stack}, which is a stack (the data structure with push and
pop operations) with one element for each function call that has been
started but has not yet completed. Each element stores things like
the value of local variables and what part of the function has not
been evaluated yet. When the evaluation of one function
body calls another function, a new element is pushed on the call stack
and it is popped off when the called function completes.

So for \verb|sum1|, there will be one call-stack element
(sometimes just called a stack frame'') for each recursive call to \verb|sum1|, i.e., the stack will be as big as the list. This is necessary because after each stack frame is popped off the caller has to,do the rest of the body’’ — namely add \verb|i| to the
recursive result and return.

Given the description so far, \verb|sum2| is no better: \verb|sum2|
makes a call to \verb|f| which then makes one recursive call for each
list element. However, when \verb|f| makes a recursive call to
\verb|f|, \emph{there is nothing more for the caller to do after the
callee returns except return the callee’s result}. This situation
is called a \emph{tail call} (let’s not try to figure out why it’s
called this) and functional languages like ML typically promise an
essential optimization: When a call is a tail call, the caller’s
stack-frame is popped \emph{before} the call — the callee’s
stack-frame just \emph{replaces} the caller’s. This makes sense: the
caller was just going to return the callee’s result anyway. Therefore,
calls to \verb|sum2| never use more than 1 stack frame.

Why do implementations of functional languages include this
optimization? By doing so, recursion can sometimes be as efficient as
a while-loop, which also does not make the call-stack bigger. The
``sometimes’’ is exactly when calls are tail calls, something you the
programmer can reason about since you can look at the code and
identify which calls are tail calls.

Tail calls do not need to be to the same function (\verb|f| can call
\verb|g|), so they are more flexible than while-loops that always have
to call'' the same loop. Using an accumulator is a common way to turn a recursive function into atail-recursive function’’ (one
where all recursive calls are tail calls), but not always. For
example, functions that process trees (instead of lists) typically
have call stacks that grow as big as the depth of a tree, but that’s
true in any language: while-loops are not very useful for processing
trees.

\section{More Examples of Tail Recursion}

Tail recursion is common for functions that process lists, but the
concept is more general. For example, here are two implementations of
the factorial function where the second one uses a tail-recursive
helper function so that it needs only a small constant amount of
call-stack space:
\begin{verbatim}
fun fact1 n = if n=0 then 1 else n * fact1(n-1)

fun fact2 n =
let fun aux(n,acc) = if n=0 then acc else aux(n-1,accn)
in
aux(n,1)
end
\end{verbatim}
It is worth noticing that \verb|fact1 4| and \verb|fact2 4| produce
the same answer even though the former performs $4 * (3 * (2 * (1 *
1)))$ and the latter performs $(((1 * 4) * 3) * 2) * 1$. We are
relying on the fact that multiplication is associative
($a
(bc)=(ab)c$) and that multiplying by 1 is the identity function
($1
x=x*1=x$). The earlier \verb|sum| example made analogous
assumptions about addition. In general, converting a
non-tail-recursive function to a tail-recursive function usually needs
associativity, but many functions are associative.

A more interesting example is this inefficient function for reversing
a list:
\begin{verbatim}
fun rev1 lst =
case lst of
[] => []
| x::xs => (rev1 xs) @ [x]
\end{verbatim}
We can recognize immediately that it is not tail-recursive since after
the recursive call it remains to append the result onto the
one-element list that holds the head of the list. Although this is
the most natural way to reverse a list recursively, the inefficiency
is caused by more than creating a call-stack of depth equal to the
argument’s length, which we will call $n$. The worse problem is that
the total amount of work performed is proportional to $n^2$, i.e.,
this is a quadratic algorithm. The reason is that appending two lists
takes time proportional to the length of the first list: it has to
traverse the first list — see our own implementations of append
discussed previously. Over all the recursive calls to \verb|rev1|, we call
\verb|@| with first arguments of length $n-1,n-2,…,1$ and the sum of
the integers from $1$ to $n-1$ is $n*(n-1)/2$.

As you learn in a data structures and algorithms course,
quadratic algorithms like this are much slower than linear algorithms
for large enough $n$. That said, if you expect $n$ to always be
small, it may be be worth valuing the programmer’s time and sticking
with a simple recursive algorithm. Else, fortunately, using the
accumulator idiom leads to an almost-as-simple linear algorithm.

\begin{verbatim}
fun rev2 lst =
let fun aux(lst,acc) =
case lst of
[] => acc
| x::xs => aux(xs, x::acc)
in
aux(lst,[])
end
\end{verbatim}

The key differences are (1) tail recursion and (2) we do only a
constant amount of work for each recursive call because \verb|::| does
not have to traverse either of its arguments.

\section{A Precise Definition of Tail Position}

While most people rely on intuition for, ``which calls are tail
calls,’’ we can be more precise by defining \emph{tail position}
recursively and saying a call is a tail call if it is in tail
position. The definition has one part for each kind of expression;
here are several parts:
\begin{itemize}
\item In \texttt{fun f(x) = e}, \texttt{e} is in tail position.
\item If an expression is not in tail position, then none of its
subexpressions are in tail position.
\item If \texttt{if e1 then e2 else e3} is in tail position, then
\texttt{e2} and \texttt{e3} are in tail position (but not \texttt{e1}).
(Case-expressions are similar.)
\item If \texttt{let b1 … bn in e end} is in tail position, then
\texttt{e} is in tail position (but no expressions in the bindings are).
\item Function-call arguments are not in tail position.
\item …
\end{itemize}