Iterative vs. Recursive coding

Steven D'Aprano steve at REMOVE-THIS-cybersource.com.au
Sun Aug 22 05:32:12 CEST 2010


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



More information about the Python-list mailing list