Skip to content

Instantly share code, notes, and snippets.

@emerleite
Forked from porcow/tail_call_optimized.py
Created July 13, 2020 18:25
Show Gist options
  • Save emerleite/0f2a68a0dea5e203b76c09ab322be74f to your computer and use it in GitHub Desktop.
Save emerleite/0f2a68a0dea5e203b76c09ab322be74f to your computer and use it in GitHub Desktop.
Tail Call Optimization Decorator (Python recipe)
## {{{ 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/ }}}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment