Tail recursion is particularly useful in programming in Scheme (a dialect of LISP). I do not know other LISP variants, so I cannot speak for them.

Because of the complexity of writing some recursive functions, they often end up being deep-recursive. Recall that tail-recursive algorithms are frequently defined as those where the value of the recursive call is equivalent to the value of the entire function. Therefore, those where some work is done on the recursive call before passing it up the stack are deep-recursive. Take the classic example of the factorial algorithm:

(define factorial
    (lambda (n)
        (if (= n 0)
            1
            (* n (factorial (- n 1))))))

Notice how the result of the recursive call is then multiplied by n. If you picture the stack, this algorithm is getting more complex every time you recurse, and after the algorithm reaches the base case, it still needs to multiply out that value by all of the preceding values of n. This is a big loss of efficiency when you compare it to:

(define factorial
    (lambda (n answer)
        (if (= n 0)
            answer
            (factorial (- n 1) (* answer n)))))

Although there is now an extra variable, this is now properly tail-recursive, as once we reach the base case and return the answer variable, we're done. Each previous recursive call just passes the value it receives back up the stack.

And if that's not enough, the Scheme interpreter is smart enough to recognize proper tail recursion and converts it into actual iteration when it's evaluating. This can result in a huge gain in efficiency, as well as reducing the amount of memory needed to evaluate these algorithms and greatly reducing the amount of time that that memory needs to be used.


Source: Professor Richard Salter of Oberlin College