Decorator which allows recursive-style functions to be iterated instead

tail_recursion.py

# tail_recurse decorator
# decorated function should return its base case, and yield the arguments for
# the recursion step (yielded value must be starable)

def tail_recurse(f):
    def inner(*args, **kwargs):
        ret = f(*args, **kwargs)
        while True:
            try:
                recursion_args = next(ret)
            except StopIteration as base_case:
                return base_case
            ret = f(*recursion_args)
    return inner



# Example: large linked list

class LinkedList:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

x = LinkedList(10000)
for i in range(9999, 0, -1):
    x = LinkedList(i, x)

# This won't exceed the recursion depth
@tail_recurse
def iter_tail(lst):
    if lst.next:
        # Must yield tuple
        yield lst.next,
    return lst.value

print(iter_tail(x))

# However, this does

def recur_tail(lst):
    if lst.next:
        return recur_tail(lst.next)
    return lst.value

try:
    print(recur_tail(x))
except RecursionError:
    print("Too long to recurse over")




# Accumulating:

@tail_recurse
def factorial(n, acc=1):
    if n == 0:
        return acc
    yield n - 1, n * acc

print(factorial(6))