Decorator which allows recursive-style functions to be iterated instead
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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