On Mon, 4 May 2009 12:34:53 am Steven D'Aprano wrote about removing tail-recursion:
In this case, the speed-up could (in principle) be by up to a factor of five or so, not a mere couple of percent.
Sorry, that "factor of five" is probably bogus. I got that for some comparisons between recursion and iteration, but the speed difference is probably not relevant to the sort of tail call optimizations we're discussing. I will *not* defend my suggestion of 5x faster, however, on the basis of my Towers of Hanoi test, I think 2x faster is conceivable. I found Guido's recent blog post of tail call optimization: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html Worthwhile reading. Also read the commenters: they make some interesting points, such as that tail call optimization is a general technique applicable to more than just recursion. Guido's largest objection to TCO is that it ruins nice stack traces when you get an exception. I must admit I've never understood this argument. Perhaps I'm missing something, but I've never considered the stack trace you get in recursive functions useful. Here's an example:
def spam(n=0): ... if n == 10: raise ValueError( ... 'Nobody expects the Spanish Inquisition!') ... spam(n+1) ... spam() Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 3, in spam File "<stdin>", line 2, in spam ValueError: Nobody expects the Spanish Inquisition!
To me, all those identical "line 3, in spam" lines are just noise. They get in the way of a nice stack trace! What is Guido seeing that I'm not? Hopefully he isn't counting them by hand to see how deep he got into the recursion! I wish there was a way to tell Python to just throw that white noise away and give me the sort of stack trace I get from a loop function. (It's not so bad when there only ten lines, but when there's 1000, you might very well fill your xterm's buffer and lose valuable history.)
def ham(n=0): ... while n < 0: ... n += 1 ... raise ValueError('Nobody expects the Spanish Inquisition!') ... ham() Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 4, in ham ValueError: Nobody expects the Spanish Inquisition!
Which of course illustrates the point that Guido's recommendation to re-write the recursion as an iterative loop by hand will have the same effect on the stack trace as iteration already does. I haven't heard anyone argue that stack traces in a while or for loop should show you the entire history of the loop, so I wonder why recursive calls should be treated as sacrosanct? (I have nothing to say about Guido's other arguments against TCO at this point, but my silence should not be interpreted as agreement.) -- Steven D'Aprano