## Thursday, April 13, 2006

### Recursion Part 2: Tail recursion, Accumulators and Iteration

The following is a part of a series of articles I had written on recursion.

This article introduces an important concept in recursion: the tail recursion. We see what tail recursion is, and where it is used. We end the article with the relationship between tail recursion and iteration.

Let us get back to the factorial program:

`int factorial(int n){    if (0 == n) {        return 1;    } else {        return n * factorial(n - 1);    }}`

As we saw in Part 1, the execution of this program goes like this:

`factorial(4)4 * factorial(3)4 * 3 * factorial(2)4 * 3 * 2 * factorial(1)4 * 3 * 2 * 1 * factorial(0)4 * 3 * 2 * 1 * 14 * 3 * 2 * 14 * 3 * 24 * 6return 24`

In this program, the multiplication with 'n' is the deferred operation (See Part 1 of this series for an introduction on deferred operations). Apart from the deferred operation, there is the recursive call to calculate factorial(n - 1).

Since the recursive call is the last step of the function, this type of recursion is called tail recursion. The name derives from the fact that the recursive call occurs at the end of the function. Oridinary tail recursion has a deferred operation and a recursive call. Pure tail recursion has no deferred operation, it only has a recursive call. The above implementation of the factorial is ordinary tail recursion because it has a deferred operation.

As we saw in Part 1, the deferred operation is carried out when the stack gets popped. Is there any way we can carry out the operation immediately and pass in the value to the function? Take a look at this implementation of factorial:

`int factorial(int n){    return factorial_acc(1, n);}int factorial_acc(int acc, int n){    if (0 == n) {        return acc;    } else {        return factorial_acc(n * acc, n - 1);    }}`

Let us trace the execution of this program to calculate factorial(4):

`factorial(4)factorial_acc(1, 4)factorial_acc(4, 3)factorial_acc(12, 2)factorial_acc(24, 1)factorial_acc(24, 0)return 24`

Notice the difference with the normal factorial implementation? In this version, there are no deferred operations. Instead, the value of the deferred operation is calculated immediately and passed as the first parameter to the recursive function. This parameter is known as the accumulator parameter (in case you were wondering, that is why it is called acc, and the function is called factorial_acc). The role of the accumulator parameter is to accumulate the result of the operations at each step. Note that this version computes the multiplication during a stack push rather than a stack pop. Nothing is done during stack pop, and so this version is pure tail recursion.

Take a look at this iterative implementation of a factorial:

`int factorial_iter(int n){    int fact = 1, i = n;    while (i > 0) {        fact = fact * i;        i--;    }    return fact;}`

Notice any similarities with the accumulator version? Look at how the variables change with each iteration while calculating factorial(4):

`factorial_iter(4)fact = 1, i = 4fact = 4, i = 3fact = 12, i = 2fact = 24, i = 1fact = 24, i = 0return 24`

Compare the fact and i variables in the iterative version with the acc and n parameters in the accumulator version. They are identical! In other words, the accumulator version simply implements a while loop using recursion!

So here is the big result: Any ordinary tail recursive program can be converted to a pure tail recursive program with accumulator, which in turn can be converted to a while loop. Thus, ordinary tail recursion and iteration are equivalent, and the above steps give us a way to convert between the two forms!

Because iteration is nothing but a special case of recursion, some languages like Lisp, Scheme and others do not have any iteration methods. There are no for loops, while loops or do-while loops in these languages. All looping is accomplished by using either ordinary or pure tail recursion! These languages have special mechanisms for optimising tail recursion so that they do not increase the stack size.

Languages like C include iterative methods and offer no special support for tail recursion. Since tail recursion is exactly equivalent to iteration, it makes sense to convert all tail recursion into iteration. However, beware of trying to convert non-tail recursion into iteration. As we shall see in later articles in this series, non-tail recursion is a very different beast altogether.

This post is a part of the selected archive.

Thomas Munro said...

"some languages like Lisp, Scheme and others do not have any iteration methods"

All good, but one small correction: As I understand it, Lisp is a whole family of languages, containing Scheme, Common Lisp and others. Scheme does as you say: it supports recursion as a way of iterating (and implementations must support tail recursion to make it efficient), whereas Common Lisp provides several kinds of raw iteration styles and is not required to optimise tail recursion.

Unknown said...

"some languages like Lisp, Scheme and others do not have any iteration methods"

As the previous poster mention, Common Lisp has several of iteration functions (macros really), i.e., do, dolist, loop, etc.

(loop for n from 1 to 10
when (oddp n)
collect n)