Python tail-call optimization, done right

It occured to me this morning to revisit the issue of tail-call-optmization using function decorators in Python. Last time I checked, the working trick involves stack inspection (works only in CPython) and throwing an exception whenever a tail call is detected. In short: non-portable and slow. I posted an enhancement here that allows for mutual recursion (function A tail-calling function B tail-calling function A …), but it did not occur to me that the stack inspection hack, clever as it is, could be improved on.

Improved on it has: Miguel Perez is reporting that his solution runs pretty much as fast as normal looping. Supports mutual recursion and is completely portable too.

clipped from groups.google.com
Please critique this tail call optimizing decorator I’ve written. I’ve tried to fix the pitfalls of other proposed decorators, and the result is this one that supports mutual recursion, does not use exceptions, stack inspection or any implementation-dependent hack, and is pretty short and fast – the fastest out of the ones I could find and try. In fact, in tail-recursive environments I tested the impact of using the decorator is difficult to even measure, as the extra time the decorator takes to run is probably saved by the better use of cache memory. The only caveat is that if used in a function that’s not called in a tail-recursive fashion, bad things will happen.
  blog it

One response to “Python tail-call optimization, done right

  1. Thanks for another informative website. Where else may I get that type of
    info written in such an ideal approach? I’ve a challenge that I am simply now working on, and
    I have been on the look out for such info.