After spending a lot of time in Scheme, it’s hard not to think in recursion from time to time. When I recently started to improve my Python skills, I missed having Scheme optimize my tail recursive calls.
For example, consider the mutually recursive functions
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 callable(a): 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.
April 2009 Update: this article has recently had some popularity. One of the more common comments is that tail_rec could be used as a decorator. In fact, this isn’t true, because
odd need access to the raw, undecorated versions of each other in the creation of the lambda.