# 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.

If you would like to be notified of future posts, you can follow me on Twitter or subscribe to my occasional emails.