Siddharta Govindaraj
/home/siddhi

/home/siddhi

Recursion Part 2: Tail recursion and Accumulators

Siddharta Govindaraj's photo
Siddharta Govindaraj
·Apr 18, 2022·

3 min read

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


Let us get back to the factorial program:

def factorial(n):
    if n == 0:
        return 1
    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, and after the recursive call, there is nothing more to execute in the function.

But even then, the actual multiplication happens only during the stack pop step, i.e. after the inner recursive call is over. So, in order to evaluate factorial(4), first it will have to execute factorial(3) and after that returns 6, then it will calculate 4 * 6 (this multiplication is the deferred operation) and return 24. This kind of tail recursion is called ordinary tail recursion.

Ordinary tail recursion has a deferred operation and a recursive call. The above implementation of the factorial is ordinary tail recursion because it has a deferred operation.

Pure tail recursion has no deferred operation, it only has a recursive call. Take a look at this implementation of factorial:

def factorial(n):
    return factorial_acc(1, n)

def factorial_acc(acc, n):
    if (n == 0):
        return acc
    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 multiplication 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. When the inner function completes, the result is directly returned by the outer function. This version is pure tail recursion.

 
Share this