Skip to content

Instantly share code, notes, and snippets.

# suminb/performance_test.py Last active Mar 22, 2019

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
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.