A very cool idea implement of the Tail Call Optimization in python

## {{{ 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 sys

class TailRecurseException:

  def __init__(self, args, kwargs):

    self.args = args

    self.kwargs = kwargs

def 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_optimized

def 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_optimized

def 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/ }}}