Tail Recursion

What Is It?

Recursion seems pretty useless, right? I mean come on – even if you do everything right (have a base case, make the problem smaller, etc etc) you can only recurse at most roughly 1000 times.

What the heck?

All of you should be asking – well, if that’s the case then screw it – I’ll just use the iterative approach!

As it turns out this is not an inherent limitation with recursion, but rather with how Python has decided to implement recursion.

Enter tail recursion. As you know, the reason recursion is limited is because every new stack frame takes up memory, and computers have a limited amount of memory allocated for the stack.

But what if you could reuse the same stack frame? Imagine your pseudocode went something like this:

def recursive_function(some_param):
    do something with the parameters

    do more calculations

    finish up all calculations

    recursive_function(some_new_param)

The critical thing here is that all calculations that use the current stack frame are done before you recurse. If this is the case, then we don’t really need a new stack frame, right? We’re done using everything we need to in this current stack frame before calling the recursive function, which means that rather than create a new stack frame, we should actually be able to use the same one… Right?

This is known as tail recursion because the recursive call occurs at the tail end of the function. Sometimes it is also called as tail call optimization. Many languages allow for this to happen by default. Java, and many functional languages like Haskell and Scala. But why not Python?

The person who invented Python is Guido van Rossum, and he is Python’s BDFL: Benevolent Dictator For Life. He has chosen, for many reasons, to not include TCO (tail call optimization) in Python. Though many disagree with him, that’s just how life is.

But that doesn’t mean we can’t do it ourselves. It just means we have to work a little harder.

A Trampoline Approach

This section assumes you’ve read everything about decorators from the last week’s bonus section. If you haven’t, none of this will make sense to you!

Let’s start with a simple program – factorial.

def fact(n, r=1):
    if n <= 1:
        return r
    else:
        return fact(n-1, n*r)

It’s fairly simple, and sure enough, fact(999) runs whereas fact(1000) produces a RuntimeError: Maximum recursion depth exceeded. So let’s make it tail recursive!

Let’s create a TailCall class that demonstrates an example.

class TailCall(object) :
    def __init__(self, call, *args, **kwargs) :
        self.call = call
        self.args = args
        self.kwargs = kwargs

    def handle(self) :
        return self.call(*self.args, **self.kwargs)

We’re not quite done yet. Next, we create a function which wraps a trampoline around any function. This is quite similar to how this worked in the decorators lecture, and it is called trampolining.

def t(f):
    def _f(*args, *kkwargs):
        ret = f(*args, **kwargs)
        while type(ret) is TailCall:
            ret = ret.handle()
        return ret
    return _f

Then, we can change our factorial function fact to do this instead.

def fact(n, r=1):
    if n <= 1:
        return r
    else:
        return TailCall(fact, n-1, n*r)

What’s going on here? Well, instead of fact(n), we are actually calling t(fact)(n)! Wow. With this, we are reusing the stack frame so we can do fact of any arbitrary number (provided you wait long enough).

This is simply a rough example of how to make this occur. You can in fact optimize this even more!

And now, you have a non-useless version of recursion! :)

TCO with Decorators

One might be tempted to use the function t that we defined above as the decorator without any changes. Try it out! Does it give you a better performance?

@t
def fact(n, r=1):
    if n <=1:
        return r
    else:
        return TailCall(fact, n-1, n*r)

On most machines, this will give you even worse than the regular, no tail-call recursion. So how do we make this better? That’s quite tricky, but if you are really curious, I highly recommend reading up on the credits section where I’ve linked you to other resources that give better solutions. (Protip: It certainly is possible to use decorators and achieve the same solution – in fact, it’s actually preferrable.)

Credits

As far as I know, Kyle Miller was one of the first to do this – and certainly the first I had heard of personally – and most of this comes from his website.

Here is Paul Butler’s explanation which is also helpful.