The code is from: http://code.activestate.com/recipes/474088/
The idea is use the exception to capture the tail call and just reserve the last call, add the exception running time, somebody test it and claimed the running time may 5 times than the non-optimal version.
## {{{ http://code.activestate.com/recipes/474088/ (r1)#!/usr/bin/env python2.4# This program shows off a python decorator(# which implements tail call optimization. It# does this by throwing an exception if it is # it's own grandparent, and catching such # exceptions to recall the stack.import sysclass TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargsdef tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back \ and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func@tail_call_optimizeddef factorial(n, acc=1): "calculate a factorial" if n == 0: return acc return factorial(n-1, n*acc)print factorial(10000)# prints a big, big number,# but doesn't hit the recursion limit.@tail_call_optimizeddef fib(i, current = 0, next = 1): if i == 0: return current else: return fib(i - 1, next, current + next)print fib(10000)# also prints a big number,# but doesn't hit the recursion limit.## end of http://code.activestate.com/recipes/474088/ }}}