Trampoline in python

gistfile1.py

# python has no tail recursion optimization.
def f(n):
  if n == 0: return 1
  return n * f(n-1)
  
f(5000)
# > RuntimeError: maximum recursion depth exceeded

# so, we can use trampoline
def f(n):
  from types import FunctionType
  def ff(n, sum):
    if n == 0: return sum
    return lambda: ff(n-1, n*sum)
  def do(n):
    fn = ff(n, 1)
    while fn.__class__ == FunctionType:
      fn = fn()
    return fn
  return do(n)
  
f(5000)
# > 42285779266055435222010642002335......