A funky attempt at a stackless combinator.

combinator_recursion.py

def stackless(body, max_depth=10_000, cached_results=None):
    class RecursiveCall(Exception): pass

    def surface(*args):
        queue = [args]
        results = cached_results or {}

        def store_argument(_, *xs):
            queue.append(xs)
            raise RecursiveCall()

        def return_cached(_, *xs):
            if xs not in results:
                # happens when there is more than one recursive call,
                # solved by repeating the procedure with one less call to calculate
                results[xs] = stackless(body, max_depth, results)(*xs)
            return results[xs]

        while len(queue) < max_depth:
            try: res = body(store_argument, *queue[-1])
            except RecursiveCall: continue
            else: break
        else: raise RuntimeError("Max depth exceeded.")

        results[queue.pop()] = res

        while queue:
            cached = queue.pop()
            results[cached] = body(return_cached, *cached)
        return results[args]
    return surface


combinator = lambda body: lambda *args: (lambda f: f(f, *args))(body)

fact_body = lambda this, n: 1 if n == 0 else n*this(this, n - 1)
fib_body = lambda this, n: n if n < 2 else this(this, n - 1) + this(this, n - 2)
tower_body = lambda this, n, src, dst, aux: [] if n == 0 else [
    *this(this, n - 1, src, aux, dst),
    f"Move the disk{n} from {src} to {dst}",
    *this(this, n - 1, aux, dst, src)
]

if __name__ == '__main__':
    assert stackless(fact_body)(20) == combinator(fact_body)(20)
    assert stackless(fib_body)(20) == combinator(fib_body)(20)
    assert stackless(tower_body)(3, 's', 'd', 'a') == combinator(tower_body)(3, 's', 'd', 'a')

    print(stackless(fib_body)(5_000))

    # exceeds 1000 recursion depth
    # print(combinator(fib_body)(5_000))