Tail Recursion in Python using Pysistence

A topic that occasionally comes up in Python development is that of tail recursion. Many functional programmers want to see tail recursion elimination added to the Python language. According to Guido, that ain’t gonna happen. And to be fair, I agree. Tail recursion can be tricky not only for new programmers, but for old timers as well.

However, that doesn’t mean that we need to give up on the concept altogether. This is a problem that is hardly new. Functional languages have been implementing tail recursion in environments hostile to it for a while now using a trampoline approach. Let’s see how the newest version of pysistence implements that algorithm:

def trampoline(func, *args, **kwargs):
    """Calls func with the given arguments.  If func returns 
       another function, it will call that function and repeat
       this process until a non-callable is returned."""
    result = func(*args, **kwargs)
    while callable(result):
        result = result()
    return result

This makes it much easier to implement things functionally (using pysistence’s functional lists):

def iter_to_plist(seq):
    seq = iter(seq)
    def inner(accum):
        try:
            return partial(inner, accum.cons(seq.next()))
        except StopIteration:
            return accum
    return inner(pysistence.make_list())

>>> trampoline(iter_to_plist, xrange(1000))
PList([999, 998, 997, 996, 995, 994, 993, 992, 991, 990, 989, 988, 987, 986, 985

That was more work than writing this in a language that does tail recursion automagically. But it wasn’t too bad now was it? Ultimately, I think this approach works for a few reasons:

  1. It’s explicit. The user is well aware of what’s happening because they’re returning a callable.
  2. It makes functional programming more natural. Instead of using true recursion and risking blowing the stack or converting this into a loop and continually reassigning to a variable, you can make the algorithm work without side effects.
  3. It lets Python stay imperative.

For me personally, this is a great set of arguments. I love Python and I love functional programming. The more functional programming I can do in Python, the better. But there are very few things in programming that are free, right? Here are some of the disadvantages:

  1. It’s ugly. I don’t deny this. But this alone is not an argument against it. If you are the kind of person who wants nothing but beautiful code, I’d argue that you’ve chosen the wrong language. Python tends to be beautiful when possible, but ugly when it has to be. Besides that this is the best you’re going to get without modifying the language itself or adding macros.
  2. It isn’t very performant. Insert your favorite quote about not needing to be blazing fast, just good enough here. Besides that, it can be optimized in C if need be.
  3. Who needs more ways to do functional programming? I’m not going to join any flamewars on this one. But I will point you to the advantages of functional programming in Python’s own functional programming HOWTO.