Does Python optimize tail recursion?
Solution 1
No, and it never will since Guido van Rossum prefers to be able to have proper tracebacks:
Tail Recursion Elimination (2009-04-22)
Final Words on Tail Calls (2009-04-27)
You can manually eliminate the recursion with a transformation like this:
>>> def trisum(n, csum):
... while True: # Change recursion to a while loop
... if n == 0:
... return csum
... n, csum = n - 1, csum + n # Update parameters instead of tail recursion
>>> trisum(1000,0)
500500
Solution 2
I published a module performing tail-call optimization (handling both tail-recursion and continuation-passing style): https://github.com/baruchel/tco
Optimizing tail-recursion in Python
It has often been claimed that tail-recursion doesn't suit the Pythonic way of coding and that one shouldn't care about how to embed it in a loop. I don't want to argue with this point of view; sometimes however I like trying or implementing new ideas as tail-recursive functions rather than with loops for various reasons (focusing on the idea rather than on the process, having twenty short functions on my screen in the same time rather than only three "Pythonic" functions, working in an interactive session rather than editing my code, etc.).
Optimizing tail-recursion in Python is in fact quite easy. While it is said to be impossible or very tricky, I think it can be achieved with elegant, short and general solutions; I even think that most of these solutions don't use Python features otherwise than they should. Clean lambda expressions working along with very standard loops lead to quick, efficient and fully usable tools for implementing tail-recursion optimization.
As a personal convenience, I wrote a small module implementing such an optimization by two different ways. I would like to discuss here about my two main functions.
The clean way: modifying the Y combinator
The Y combinator is well known; it allows to use lambda functions in a recursive manner, but it doesn't allow by itself to embed recursive calls in a loop. Lambda calculus alone can't do such a thing. A slight change in the Y combinator however can protect the recursive call to be actually evaluated. Evaluation can thus be delayed.
Here is the famous expression for the Y combinator:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
With a very slight change, I could get:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
Instead of calling itself, the function f now returns a function performing the very same call, but since it returns it, the evaluation can be done later from outside.
My code is:
def bet(func):
b = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = b(*args)
while callable(out):
out = out()
return out
return wrapper
The function can be used in the following way; here are two examples with tail-recursive versions of factorial and Fibonacci:
>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55
Obviously recursion depth isn't an issue any longer:
>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42
This is of course the single real purpose of the function.
Only one thing can't be done with this optimization: it can't be used with a tail-recursive function evaluating to another function (this comes from the fact that callable returned objects are all handled as further recursive calls with no distinction). Since I usually don't need such a feature, I am very happy with the code above. However, in order to provide a more general module, I thought a little more in order to find some workaround for this issue (see next section).
Concerning the speed of this process (which isn't the real issue however), it happens to be quite good; tail-recursive functions are even evaluated much quicker than with the following code using simpler expressions:
def bet1(func):
def wrapper(*args):
out = func(lambda *x: lambda: x)(*args)
while callable(out):
out = func(lambda *x: lambda: x)(*out())
return out
return wrapper
I think that evaluating one expression, even complicated, is much quicker than evaluating several simple expressions, which is the case in this second version. I didn't keep this new function in my module, and I see no circumstances where it could be used rather than the "official" one.
Continuation passing style with exceptions
Here is a more general function; it is able to handle all tail-recursive functions, including those returning other functions. Recursive calls are recognized from other return values by the use of exceptions. This solutions is slower than the previous one; a quicker code could probably be written by using some special values as "flags" being detected in the main loop, but I don't like the idea of using special values or internal keywords. There is some funny interpretation of using exceptions: if Python doesn't like tail-recursive calls, an exception should be raised when a tail-recursive call does occur, and the Pythonic way will be to catch the exception in order to find some clean solution, which is actually what happens here...
class _RecursiveCall(Exception):
def __init__(self, *args):
self.args = args
def _recursiveCallback(*args):
raise _RecursiveCall(*args)
def bet0(func):
def wrapper(*args):
while True:
try:
return func(_recursiveCallback)(*args)
except _RecursiveCall as e:
args = e.args
return wrapper
Now all functions can be used. In the following example, f(n)
is evaluated to the
identity function for any positive value of n:
>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42
Of course, it could be argued that exceptions are not intended to be used for intentionally
redirecting the interpreter (as a kind of goto
statement or probably rather a kind of
continuation passing style), which I have to admit. But, again,
I find funny the idea of using try
with a single line being a return
statement: we try to return
something (normal behaviour) but we can't do it because of a recursive call occurring (exception).
Initial answer (2013-08-29).
I wrote a very small plugin for handling tail recursion. You may find it with my explanations there: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs
It can embed a lambda function written with a tail recursion style in another function which will evaluate it as a loop.
The most interesting feature in this small function, in my humble opinion, is that the function doesn't rely on some dirty programming hack but on mere lambda calculus: the behaviour of the function is changed to another one when inserted in another lambda function which looks very like the Y combinator.
Solution 3
The word of Guido is at http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
I recently posted an entry in my Python History blog on the origins of Python's functional features. A side remark about not supporting tail recursion elimination (TRE) immediately sparked several comments about what a pity it is that Python doesn't do this, including links to recent blog entries by others trying to "prove" that TRE can be added to Python easily. So let me defend my position (which is that I don't want TRE in the language). If you want a short answer, it's simply unpythonic. Here's the long answer:
Solution 4
CPython does not and will probably never support tail call optimization based on Guido van Rossum's statements on the subject.
I've heard arguments that it makes debugging more difficult because of how it modifies the stack trace.
Solution 5
Besides optimizing tail recursion, you can set the recursion depth manually by:
import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
Related videos on Youtube
Jordan Mack
Senior Software Engineer specializing in Full-Stack Blockchain Development. ♥ Rust. Cryptocurrency since 2011. Founder of RigidBit blockchain. Health nut. Libertarian. Lifelong learner. https://www.jordanmack.info/
Updated on March 20, 2021Comments
-
Jordan Mack about 3 years
I have the following piece of code which fails with the following error:
RuntimeError: maximum recursion depth exceeded
I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been successful if a TCO had taken place.
def trisum(n, csum): if n == 0: return csum else: return trisum(n - 1, csum + n) print(trisum(1000, 0))
Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?
-
Wessie over 11 yearsPython has no TCO implemented, It's believed to be too complex to implement in a dynamic language such as Python.
-
kaspersky over 11 yearsWhat is the code for initial recursion, which failed?
-
Admin over 11 years@Wessie TCO is simple regard of how dynamic or static the language is. Lua, for example, also does it. You merely need to recognize tail calls (pretty simple, both at AST level and at bytecode level), and then re-use the current stack frame instead of creating a new one (also simple, actually even simpler in interpreters than in native code).
-
Admin over 11 yearsOh, one nitpick: You talk exclusively about tail recursion, but use the acronym "TCO", which means tail call optimization and applies to any instance of
return func(...)
(explicitly or implicitly), whether it's recursive or not. TCO is a proper superset of TRE, and more useful (e.g. it makes continuation passing style feasible, which TRE can't), and not much harder to implement. -
jsbueno about 11 yearsHere is a hackish way to implement it - a decorator using exception raising to throw execution frames away: metapython.blogspot.com.br/2010/11/…
-
ctrl-alt-delor almost 10 yearsLisp has it, but I think wanting good trace backs is the trade off, you can not have both.
-
Kevin almost 9 yearsIf you restrict yourself to tail recursion, I don't think a proper traceback is super-useful. You have a call to
foo
from inside a call tofoo
from inside tofoo
from inside a call tofoo
... I don't think any useful information would be lost from losing this. -
Alexey about 7 yearsI have recently learned about Coconut but have not tried it yet. It looks worth taking a look at. It is claimed to have tail recursion optimisation.
-
-
Admin over 11 years@mux CPython is the reference implementation of the programming language Python. There are other implementations (such as PyPy, IronPython, and Jython), which implement the same language but differ in implementation details. The distinction is useful here because (in theory) it's possible to create an alternative Python implementation that does TCO. I'm not aware of anyone even thinking about it though, and usefulness would be limited as code relying on it would break on all other Python implementations.
-
Jon Clements over 11 yearsOr if you're going to transform it like that - just:
from operator import add; reduce(add, xrange(n + 1), csum)
? -
John La Rooy over 10 years@JonClements, that works in this particular example. The transformation to a while loop works for tail recursion in general cases.
-
Basic over 9 years+1 For being the correct answer but this seems like an incredibly bone-headed design decision. The reasons given seem to boil down to "it's hard to do given how python is interpreted and I don't like it anyway so there!"
-
Adam Donahue over 9 yearsAnd herein lies the problem with so-called BDsFL.
-
Mark Ransom over 9 years@AdamDonahue have you been perfectly satisfied with every decision that's come from a committee? At least you get a reasoned and authoritative explanation from the BDFL.
-
Adam Donahue over 9 yearsNo, of course not, but they strike me as more even-handed. This from a prescriptivist, not a descriptivist. The irony.
-
Basic over 8 years@jwg So... What? You have to write a language before you can comment on poor design decisions? Hardly seems logical or practical. I assume from your comment that you have no opinion about any features (or lack thereof) in any language ever written?
-
hert over 7 yearsWhy don't you just use jQuery?
-
Veky over 7 years@Basic No, but you have to read the article you're commenting on. It seems very strongly that you didn't actually read it, considering how it "boils down" to you. (You might actually need to read both of the linked articles, unfortunately, since some arguments are spread over both.) It has almost nothing to do with implementation of the language, but everything to do with the intended semantics.
-
Veky over 7 yearsBecause it also doesn't offer TCO? :-D stackoverflow.com/questions/3660577/…
-
Basic over 7 years@Veky I have read the article I was commenting on. Just because GVR decides to highlight the flaws with the approaches some people have taken to work around this gap in the language, I don't see how that becomes an argument against a feature. You say "It has almost nothing to do with implementation of the language, but everything to do with the intended semantics." which brings me back to my first point. Tail recursion can be an elegant way to solve a problem. Refusing to support it because the syntax wouldn't be "pythonic" seems pretty bone-headed.
-
Veky over 7 yearsOk, I give up. Now you're talking about syntax, which is even less relevant to original Guido's point than the implementation. On the other hand, you never even mention debugging, which is Guido's main argument. It's obvious we look at the same thing and see it very differently. A matter of perspective, I guess. :-)
-
Mangohero1 over 6 yearsinteresting... I'm curious but how does this eventually break out of the
while
loop? There's no break explicitly define or nothing that would appear to makewhile True
beFalse
... -
John La Rooy over 6 years@Mangohero1, the loop is broken by the
return
. Note that -ve values ofn
will loop forever. -
Alexey almost 6 yearsCould you, please, provide an example of defining a function (preferably in way similar to a normal definition) which tail-calls one of several other functions based on some condition, using your method? Also, can your wrapping function
bet0
be used as a decorator for class methods? -
Thomas Baruchel almost 6 years@Alexey I am not sure I can write code in a block-style inside a comment, but you can of course use the
def
syntax for your functions, and actually the last example above relies on a condition. In my post baruchel.github.io/python/2015/11/07/… you can see a paragraph beginning with "Of course you could object that nobody would write such a code" where I give an example with the usual definition syntax. For the second part of your question, I have to think about it a little more since I haven't spent time in that for a while. Regards. -
josiah almost 5 yearsSome important arguments in favor of tail recursion, outside of TCO being supported or not, are being overlooked. First, some algorithms are so difficult to express non-recursively that it's not practical to write them that way (e.g. Karatsuba multiplication). Secondly, tail recursion should still be preferred over other types of recursion even if TCO isn't supported by the language because it minimizes the size of each recursive call on the stack (so I have to disagree with Baruchel's answer, below, on that one point - you should care where the recursive call happens even without TCO).
-
josiah almost 5 yearsYou should care where the recursive call happens in your function even if you are using a non-TCO language implementation. This is because the portion of the function that occurs after the recursive call is the portion that needs to get stored on the stack. Therefore, making your function tail-recursive minimizes the amount of information you have to store per recursive call, which gives you more room to have large recursive call stacks if you need them.
-
wjandrea almost 4 yearsWhy do you do
while True: if n == 0: return csum; ...
instead ofwhile n != 0: ...; return csum
? Just curious. -
tf3 about 3 years“Third, I don't believe in recursion as the basis of all programming”. This looks like the real reason