On Sat, 21 Aug 2010 19:09:52 -0500, John Bokma wrote: > this means that Python should eliminate / optimize tail > recursion.
There have been various suggestions to add tail recursion optimization to the language. Two problems: * It throws away information from tracebacks if the recursive function fails; and * nobody willing to do the work is willing to champion it sufficiently to get it approved in the face of opposition due to the above. If you're like me, you're probably thinking that the traceback from an exception in a recursive function isn't terribly useful. Who needs to see something like this? >>> recurse(10) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 3, in recurse File "<stdin>", line 2, in recurse ValueError *yawn* Would it really matter if Python truncated the stack trace to just the last line? I don't think so. But this is not the only sort of tail-call recursion, and a traceback like the following is useful: >>> recurse(4) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 5, in recurse File "<stdin>", line 3, in f File "<stdin>", line 5, in recurse File "<stdin>", line 3, in f File "<stdin>", line 5, in recurse File "<stdin>", line 3, in f File "<stdin>", line 4, in recurse File "<stdin>", line 2, in g ValueError If all you saw was the last line (the call to g), debugging the exception would be significantly harder. That's a real traceback, by the way, not faked, although it is a contrived example which I shan't bother to share. The point is not my specific recursive example, but that not all recursion is direct and therefore losing the stack traces can be a real cost. There's more information here: http://www.tratt.net/laurie/tech_articles/articles/tail_call_optimization I think it says something that (so far as I know) none of the other Python implementations have added this optimization. Java doesn't have it either. Me personally, I'd like to see either a (preferably) run-time setting or compile-time switch that enables/disables this optimization. Even an explicit decorator would be fine. And lo and behold: http://hircus.wordpress.com/2008/06/21/python-tail-call-optimization-done-right/ http://groups.google.com/group/comp.lang.python/msg/9b047d1392f2b8ec Add it to your bag of tricks and have fun. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
