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.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

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 * 1
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
return 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 = 4
fact = 4, i = 3
fact = 12, i = 2
fact = 24, i = 1
fact = 24, i = 0
return 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.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.