Lecture Notes on Tail Recursion

Tail recursion

A tail-recursive call (or tail call) is a recursive call that is the last action of the calling function, i.e. such that the result returned from the recursive call will also be caller's result. Tail calls are interesting because most compilers for functional languages will implement a tail call as a simple branch, re-using the stack space of the caller instead of allocating a new stack frame for the recursive call. This means that a loop implemented as a tail-recursive function compiles into the same machine code as an equivalent while loop. [B.Pierce]

Example:

sumAux [] c = c
sumAux (x:xs) c = sumAux xs (c+x)

sumIter xs = sumAux xs 0

The function SumAux is tail recursive because after the recursive call there is nothing else left to do.

If we define the same function without tail recursion we get

sum [] = 0
sum (x:xs) = x + (sum xs)

Try and see by yourself what happens during the evaluation of sum on a list, say (2 4 6 1 3). You need to leave a number of additions uncompleted until you reach the base case. When the base case is reached, all the additions can be made.
In a sense, you need a stack to remember what "remains to be computed".
Now, mimic the evaluation of sumIter on the same input. You need to remember nothing, since no operation is left to be computed.

Tail recursion, in a sense, correspond to the notion of iteration in functional programming (indeed you can translate tail recursive functions in an imperative language by using a simple loop. The translation of a non tail recursive function, instead, will definitely use a stack, or something equivalent.)

In the function sumAux (used by sumIter) the argument 'c' plays the role of an accumulator. In each recursive call a shorter list is passed to aux, while the accumulator is "extended" with the first element of the list. In a sense, each recursive call is like an iteration that modifies a variable, the accumulator, and the "assignment" of a new value to the accumulator is mimicked by passing the new value as second argument of the recursive call.

It is possible to provide iterative versions of all the functions, not always easily.

Let us see a few tail recursive versions of well known functions

reverseIterAux [] as = as
reverseIterAux (x:xs) as = reverseIterAux xs (x:as)

reverseIter xs = reverseIterAux xs []

appendIterAux [] [] as = reverseIter as
appendIterAux [] ys as = appendIterAux ys [] 
appendIterAux (x:xs) ys  as = appendIterAux xs ys (x:as)

appendIter xs ys = appendIter xs ys []

In this definitions there is a "hidden" iterative imperative algorithm.
Tail recursion can be thought of as the functional counterpart of Iteration.