Skip to content

Instantly share code, notes, and snippets.

@koutoftimer
Last active November 6, 2016 22:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save koutoftimer/125cba12b9e1131c68331fe59f671f96 to your computer and use it in GitHub Desktop.
Save koutoftimer/125cba12b9e1131c68331fe59f671f96 to your computer and use it in GitHub Desktop.
Resolve tail recursion depth limitation in python
"""
Thanks to Kyle Miller for his article "Tail call recursion in Python" [1].
Despite how good is to remove this limitation, probably, you have to be
aware of why this feature is not officially supported. [2]
[1]: http://www.kylem.net/programming/tailcall.html
[2]: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
"""
class TailCall(object):
def __init__(self, __function__):
self.__function__ = __function__
self.args = None
self.kwargs = None
self.has_params = False
def __call__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
self.has_params = True
return self
def __handle__(self):
if not self.has_params:
raise TypeError
if type(self.__function__) is TailCaller:
return self.__function__.call(*self.args, **self.kwargs)
return self.__function__(*self.args, **self.kwargs)
class TailCaller(object):
def __init__(self, call):
self.call = call
def __call__(self, *args, **kwargs):
ret = self.call(*args, **kwargs)
while type(ret) is TailCall:
ret = ret.__handle__()
return ret
@TailCaller
def factorial(n, prev=1):
if n < 2:
return prev
return TailCall(factorial)(n-1, n * prev)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment