Skip to content

Instantly share code, notes, and snippets.

Last active January 23, 2017 08:09
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save louisswarren/27d8e03cbfe867cd22750348e1781857 to your computer and use it in GitHub Desktop.
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:
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 = next
x = LinkedList(10000)
for i in range(9999, 0, -1):
x = LinkedList(i, x)
# This won't exceed the recursion depth
def iter_tail(lst):
# Must yield tuple
return lst.value
# However, this does
def recur_tail(lst):
return recur_tail(
return lst.value
except RecursionError:
print("Too long to recurse over")
# Accumulating:
def factorial(n, acc=1):
if n == 0:
return acc
yield n - 1, n * acc
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment