Skip to content

Instantly share code, notes, and snippets.

@rafaelbeckel
Last active February 25, 2020 10:02
Show Gist options
  • Save rafaelbeckel/4ed8d7822d22cf6fe4103cc08b19621b to your computer and use it in GitHub Desktop.
Save rafaelbeckel/4ed8d7822d22cf6fe4103cc08b19621b to your computer and use it in GitHub Desktop.
A simple tail recursive class to overcome Python's recursion limit
"""
Implements tail recursion decorator to overcome Python's recursive limit.
This is a simple version that supports single-loop recursion functions like
fibonacci or factorial. There is also a more complex decorator with support
for branching published here:
https://gist.github.com/rafaelbeckel/9849184c5a8e7832b659e3c0e3ee7d3e
Usage:
------
@Recursive.method
def my_method(arg1, arg2):
# ... some logic
Recursive.call(arg1, arg2)
"""
class Recursion(Exception):
def __init__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
class Recursive:
def __init__(self, function):
self.function = function
def __call__(self, *args, **kwargs):
while True:
try:
return self.function(*args, **kwargs)
except Recursion as r:
args = r.args
kwargs = r.kwargs
continue
@staticmethod
def call(*args, **kwargs):
raise Recursion(*args, **kwargs)
@rafaelbeckel
Copy link
Author

rafaelbeckel commented Feb 18, 2020

Usage:

from recursion import Recursive

class MyClass:
    @Recursive
    def factorial(n, accumulator=1):
        if n == 0:
            return accumulator
        Recursive.call(n-1, accumulator=accumulator*n)

Credits:
Adapted from https://chrispenner.ca/posts/python-tail-recursion

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment