Siddharta Govindaraj
/home/siddhi

/home/siddhi

Recursion Part 4: Accumulators and Iteration

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

2 min read

In the previous post we were looking at tail call optimisation of this factorial implementation

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)

and we saw that the call stack was like this

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

When there is tail call optimisation this whole call stack can be collapsed into a single stack where each stack frame replaces the previous one.

Now let us look at an iterative version of the factorial

def factorial_iter(n):
    fact = 1
    i = n

    while i > 0:
        fact = fact * i
        i = i - 1
    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 above to the call stack of the accumulator version and you will find that they are identical. Here the fact variable plays the role of the accumulator.

So here is the important 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!

In other words, iteration is just a special case of recursion. Some languages like Scheme do not have any looping statements at all. No for loop, no while loop. They do have tail call optimisation, so you are expected to do all the looping with tail recursion.

In other languages like C, Java and Python, there is no special support for tail call optimisation. Instead these languages provide iterative looping constructs which are preferred over tail recursion.

Sometimes, certain algorithms are easier to express in a tail recursive form. Since tail recursion is equivalent to iteration, you can always convert the code back and forth between the two forms.

 
Share this