Tail recursion in Python

After spending a lot of time in Scheme, it’s hard not to think in recursion. So recently when I started to improve my Python skills, I missed having Scheme optimize my tail recursive calls.

For example, consider the mutually recursive functions even and odd. You know a number, n, is even if it is 0, or if n - 1 is odd. Similarly, you know a number is not odd if it is 0, and that it is odd if n - 1 is even. This translates to the python code:

def even(x): if x == 0: return True else: return odd(x - 1) def odd(x): if x == 0: return False else: return even(x - 1)

This code works, but only for x < 1000, because Python limits the recursion depth to 1000. As it turns out, it is easy to get around this limitation. Included below is a generic tail_rec function that could be used for most cases where you need tail recursion, and an example of it used for the odd/even problem.

def tail_rec(fun): def tail(fun): a = fun while type(a) == type(tail): a = a() return a return (lambda x: tail(fun(x))) def tail_even(x): if x == 0: return True else: return (lambda: tail_odd(x - 1)) def tail_odd(x): if x == 0: return False else: return (lambda: tail_even(x - 1)) even = tail_rec(tail_even) odd = tail_rec(tail_odd)

It’s not as pretty as the Scheme version, but it does the trick. Of course, the odd/even functions are just for the sake of a simple example and have no real-world use, but the tail_rec function could be used in practice.