Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.