xtao · March 17, 2018 17:09 · Mar 17, 2018
diff --git a/tail_recursive.py b/tail_recursive.py
@@ -0,0 +1,94 @@
+# http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/
+
+#!/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.
+
+
+
+class Recurse(Exception):
+    def __init__(self, *args, **kwargs):
+        self.args = args
+        self.kwargs = kwargs
+
+def recurse(*args, **kwargs):
+    raise Recurse(*args, **kwargs)
+
+def tail_recursive(f):
+    def decorated(*args, **kwargs):
+        while True:
+            try:
+                return f(*args, **kwargs)
+            except Recurse as r:
+                args = r.args
+                kwargs = r.kwargs
+                continue
+    return decorated
+
+# http://chrispenner.ca/posts/python-tail-recursion
+
+from tail_recursion import tail_recursive, recurse
+
+# Normal recursion depth maxes out at 980, this one works indefinitely
+@tail_recursive
+def factorial(n, accumulator=1):
+    if n == 0:
+        return accumulator
+    recurse(n-1, accumulator=accumulator*n)