A new tail recursion decorator that eliminates tail calls for recursive functions is introduced.
Python, 63 lines
It is about 2 months ago that Crutcher Dunnavant published a cute tail recursion decorator that eliminates tail calls for recursive functions in Python i.e. turning recursion into iteration . The new one gets rid of catching exceptions and is faster. The source code shows two versions. The first one uses stack frame inspections just like Crutchers decorator, the second one abandones those and runs twice as fast.
Warning: the optimization comes at its price. The dumbed down lookup procedure causes brittleness in certain cases and different @tail_recursion decorators can interfere as in the following counter example:
@tail_recursion def even(n): if n == 0: return True else: return odd(n-1)
@tail_recursion def odd(n): if n == 0: return False else: return even(n-1)
Commenting out one of these decorators let it work again. Crutchers decorator works in both cases and shows the expected bounded sized stack behaviour.
Note also that these decorators are not optimizing and for small argument values they are actually far slower.