# Recursion Part 4: Accumulators and Iteration

Siddharta Govindaraj
·Apr 19, 2022·

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.