Decorator which allows recursive-style functions to be iterated instead
# 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment