Skip to content

Instantly share code, notes, and snippets.

@suminb
Last active March 22, 2019 03:29
Show Gist options
  • Save suminb/7118ffb2251b07701b4f8bb9dbd7f899 to your computer and use it in GitHub Desktop.
Save suminb/7118ffb2251b07701b4f8bb9dbd7f899 to your computer and use it in GitHub Desktop.
Tail Recursion Elimination in Python
import timeit
recursive_code = """
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
factorial(n)
"""
tail_recursive_code = """
def factorial(n, result=1):
if n == 0:
return result
else:
return factorial(n - 1, result * n)
factorial(n)
"""
tail_recursion_eliminated_code = """
from trlib import tail_recursion
@tail_recursion
def factorial(n, result=1):
from trlib import recurse as factorial
if n == 0:
return result
else:
return factorial(n - 1, result * n)
factorial(n)
"""
number = 10000
for varname in ('recursive_code', 'tail_recursive_code',
'tail_recursion_eliminated_code'):
statement = globals()[varname]
timer = timeit.Timer(stmt=statement, setup='n = 800')
time = timer.timeit(number=number)
print(varname)
print('{:.3f} ms/pass\n'.format(time / number * 1000))
from trlib import tail_recursion
@tail_recursion
def factorial(n, result=1):
from trlib import recurse as factorial
if n == 0:
return result
else:
return factorial(n - 1, result * n)
class Recursion(Exception):
def __init__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
def recurse(*args, **kwargs):
raise Recursion(*args, **kwargs)
def tail_recursion(f):
def wrapper(*args, **kwargs):
while True:
try:
return f(*args, **kwargs)
except Recursion as r:
args = r.args
kwargs = r.kwargs
return wrapper
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment