Tail Recursion in Python

Paul Butler – December 13, 2007

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 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 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 even and odd need access to the raw, undecorated versions of each other in the creation of the lambda.


Want to be notified of future posts? Subscribe to my updates or follow me on Twitter.