Siddharta Govindaraj
/home/siddhi

/home/siddhi

Recursion Part 3: Tail call optimisation

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

2 min read

In the previous part, we implemented a factorial program using pure tail recursion and accumulators. This was the code

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)

When we run this code to calculate factorial(4), the stack trace looks 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

The main difference in pure tail optimisation is that there is no deferred operation, when the inner function returns a value, the outer function directly returns that same value without any further computation. Therefore once we go into the inner function, we no longer require the stack frame for the outer function as it will never to used again in the computation.

If we were to run the above code in Python with a large value of 'n' after some time we will get a stack overflow error. This is because as we go deeper and deeper into the recursion, the language runtime keeps all the stack frames alive until finally it hits the limit.

However, in many functional programming languages this does not happen. The runtime detects when a pure tail call recursion happens. Then when they go into the inner function, they remove the stack of the outer function. So at any point of time during the recursion, only the current call stack is maintained, all the previous ones are gone. In these languages you can do pure tail call recursion forever without hitting any stack overflow.

This technique is called tail call optimisation. If the language you are working with supports tail call optimisation, you can happily use these recursive versions. What if the language you are using does not support it? Well, we shall see in the next article of this series that should be out in a couple of days.

 
Share this