A more powerful version of the tail recursion decorator with branching support

tail_recursion_with_branching.py

from functools import wraps
from collections import deque

"""
Implements tail recursion decorator to overcome Python's recursive limit.

This is similar to my previous, simpler one:
https://gist.github.com/rafaelbeckel/4ed8d7822d22cf6fe4103cc08b19621b

The difference of this version is that it now adds support for stacking up
lots of recursive calls and then firing a recursion that will execute them 
in the right order. 

It can be useful for tree-traversal or divide-and-conquer algorithms where
you may need to branch out to different recursion paths, while keeping the 
context from previous calls. The old solution works for simple single-loop
recursion like fibonacci, but it destroys information about call hierarchy.

Usage: 
------
@Recursive.method
def my_method(arg1, arg2):
    # ... some logic
    # adds method to call_stack:
    Recursive.call(my_method, [arg1, arg2]) # this will run first
    Recursive.call(my_method, [arg1, arg2]) # this will run later
    # ...
    Recursive.stop() # execute all chained methods
"""

class Recursion(Exception):
    def __init__(self, *args):
        self.args = args


class CallStack():
    def __init__(self):
        self.start = None
        self.execution_queue = deque()
        self.call_stack = deque()

    def set_start(self, function):
        self.start = function

    def is_empty(self):
        return len(self.execution_queue) == 0 \
            and len(self.call_stack) == 0

    def add(self, function, args):
        if self.start is None:
            self.start = function
        self.call_stack.appendleft((function, [*args]))

    def run(self, cls):
        self.execution_queue.extendleft(self.call_stack)
        self.call_stack.clear()

        function, args = self.execution_queue.popleft()

        if function.__name__ == self.start.__name__:
            return self.start(cls, *args)
        else:
            return function(*args)


_stack = CallStack()
class Recursive():
    @staticmethod
    def method(function):
        _stack.set_start(function)
        @wraps(function)
        def __wrapper__(self, *args):
            _stack.add(_stack.start, [*args, 0])
            while not _stack.is_empty():
                try:
                    return _stack.run(self)
                except Recursion as r:
                    continue
        return __wrapper__

    @staticmethod
    def call(function, *args):
        _stack.add(function, *args)

    @staticmethod
    def stop():
        raise Recursion()

In the future, I may redesign it to place the global _stack variable inside the class instead.
I'd like to do it without changing the decorator interface, and maybe automatically fire the stop() call after a function ends.

For now, it's serving me well and I hope it can be useful to someone else.