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