Skip to content

Instantly share code, notes, and snippets.

@ionelmc
Forked from orf/tail_call.py
Created Oct 15, 2013
Embed
What would you like to do?
import functools
def tail_call(tuple_return=False):
def __wrapper(func):
def _optimize_partial(*args):
"""
I replace the reference to the wrapped function with a functools.partial object
so that it doesn't actually call itself upon returning, allowing us to do it instead.
Advantages: Theoretically needs no code changes and is more understandable
Disadvantages: Its startup overhead is higher and its a bit slower. Also can only call
recursively when returning, so return func(1) + func(2) will not work.
"""
func_globals = func.func_globals
func_name = func.func_name
old_reference = func_globals[func_name]
func_globals[func_name] = lambda *args: args
to_execute = func(*args)
while to_execute.__class__ is tuple:
to_execute = func(*to_execute)
func_globals[func_name] = old_reference
return to_execute
def _optimize_tuple(*args):
"""
This way requires the function to return a tuple of arguments to be passed to the next
call.
Advantages: Very little overhead, faster than plain recursion
Disadvantages: Needs code changes, not as readable, no support for keyword arguments (yet)
"""
while args.__class__ is tuple: # Faster than isinstance()!
#while isinstance(args, tuple):
args = func(*args)
return args
if tuple_return:
functools.update_wrapper(_optimize_tuple, func)
return _optimize_tuple
else:
functools.update_wrapper(_optimize_partial, func)
return _optimize_partial
return __wrapper
@tail_call()
def test_fib_optimize(i, current=0, next=1):
if i == 0:
return current
else:
return test_fib_optimize(i - 1, next, current + next)
@tail_call(tuple_return=True)
def test_fib_tuple_optimized(i, current=0, next=1):
if i == 0:
return current
else:
return i - 1, next, current + next,
def test_fib_no_optimize(i, current=0, next=1):
if i == 0:
return current
else:
return test_fib_no_optimize(i - 1, next, current + next)
import timeit
import sys
sys.setrecursionlimit(8000)
for func in (test_fib_optimize, test_fib_tuple_optimized, test_fib_no_optimize):
print func.func_name, timeit.timeit(functools.partial(func, 1700), number=1000)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment