Tail recursion in Python
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.
I’m new to Python but not to programming, and I know the above is just an example for recursion but stile you could just modulo the number by 2 if 1 then odd else even
Nick, you’re right. Another way would be to use a bitwise “and” (for example, “x & 1 == 0″ would be the even function). I didn’t want to use odd/even at first as the demonstration problem, since it is not a recursive problem in nature. However, of all the examples of mutual recursion I had seen and could think of, it was the most straightforward, and I figured anything more complicated would distract from the concept.
What you’re describing is basically Trampolined Style. http://www.cs.indiana.edu/~dfried/ts.ps has more.
Take a look at stackless. Basically they took the standard CPython and modified it for microthreads. One of the things they changed when they did this was to not use C stack frames for function calls like CPython does hence the name stackless, in doing so the recursion depth issue is gone.
I agree with the stackless comment. It allows unbounded recursion, and what’s more, it even optimizes tail call recursion.
http://www.stackless.com/spcpaper.htm
Old good trampolines :)
praxis? ??…
tail recursion in python, ??? ?? ???….
praxis? ??…
tail recursion in python, ??? ?? ???….
“a = a()”? Objectivist? ;-)
popurls.com // popular today…
story has entered the popular today section on popurls.com…
So you explicitly store state rather than implicitly on the stack. This is better as I noted here:
http://www.pixelbeat.org/programming/functional_python_state.html
Why not setting your recursion limit higher?
From the python doc:
sys.setrecursionlimit(limit)
Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.
Interesting technique – thanks!
Brian, thanks. Stackless looks pretty cool.
ythefoe, that works, but only if you have the memory and you know in advance an upper bound on the size of the stack. Neither of these are always the case.
See Python Tail Recursion Decorators.
For instance:
http://code.activestate.com/recipes/496691/
Regards,
Rich