Can generators be recursive?

Question

I naively tried to create a recursive generator. Didn't work. This is what I did:

def recursive_generator(lis):
    yield lis[0]
    recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)

All I got was the first item 6.

Is there a way to make such code work? Essentially transferring the yield command to the level above in a recursion scheme?

Solution 1

Try this:

def recursive_generator(lis):
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)

I should point out this doesn't work because of a bug in your function. It should probably include a check that lis isn't empty, as shown below:

def recursive_generator(lis):
    if lis:
        yield lis[0]
        yield from recursive_generator(lis[1:])

In case you are on Python 2.7 and don't have yield from, check this question out.

Solution 2

Why your code didn't do the job

In your code, the generator function:

1. returns (yields) the first value of the list
2. then it creates a new iterator object calling the same generator function, passing a slice of the list to it
3. and then stops

The second instance of the iterator, the one recursively created, is never being iterated over. That's why you only got the first item of the list.

A generator function is useful to automatically create an iterator object (an object that implements the iterator protocol), but then you need to iterate over it: either manually calling the next() method on the object or by means of a loop statement that will automatically use the iterator protocol.

So, can we recursively call a generator?

The answer is yes. Now back to your code, if you really want to do this with a generator function, I guess you could try:

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it... 
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list.
            yield i
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Note: the items are returned in reversed order, so you might want to use some_list.reverse() before calling the generator the first time.

The important thing to note in this example is: the generator function recursively calls itself in a for loop, which sees an iterator and automatically uses the iteration protocol on it, so it actually gets values from it.

This works, but I think this is really not useful. We are using a generator function to iterate over a list and just get the items out, one at a time, but... a list is an iterable itself, so no need for generators! Of course I get it, this is just an example, maybe there are useful applications of this idea.

Another example

Let's recycle the previous example (for lazyness). Lets say we need to print the items in a list, adding to every item the count of previous items (just a random example, not necessarily useful).

The code would be:

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it...
    and adding to every item the count of previous items in the list
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list, but add 1 first. 
            # Every recursive iteration will add 1, so we basically add the count of iterations.
            yield i + 1
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Now, as you can see, the generator function is actually doing something before returning list items AND the use of recursion starts to make sense. Still, just a stupid example, but you get the idea.

Note: off course, in this stupid example the list is expected to contain only numbers. If you really want to go try and break it, just put in a string in some_list and have fun. Again, this is only an example, not production code!

Solution 3

Recursive generators are useful for traversing non-linear structures. For example, let a binary tree be either None or a tuple of value, left tree, right tree. A recursive generator is the easiest way to visit all nodes. Example:

tree = (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))),
        (6, None, (7, (8, (9, None, None), None), None)))

def visit(tree):  # 
    if tree is not None:
        try:
            value, left, right = tree
        except ValueError:  # wrong number to unpack
            print("Bad tree:", tree)
        else:  # The following is one of 3 possible orders.
            yield from visit(left)
            yield value  # Put this first or last for different orders.
            yield from visit(right)

print(list(visit(tree)))

# prints nodes in the correct order for 'yield value' in the middle.
# [1, 3, 2, 5, 4, 0, 6, 9, 8, 7]

Edit: replace if tree with if tree is not None to catch other false values as errors.

Edit 2: about putting the recursive calls in the try: clause (comment by @jpmc26).

For bad nodes, the code above just logs the ValueError and continues. If, for instance, (9,None,None) is replaced by (9,None), the output is

Bad tree: (9, None)
[1, 3, 2, 5, 4, 0, 6, 8, 7]

More typical would be to reraise after logging, making the output be

Bad tree: (9, None)
Traceback (most recent call last):
  File "F:\Python\a\tem4.py", line 16, in <module>
    print(list(visit(tree)))
  File "F:\Python\a\tem4.py", line 14, in visit
    yield from visit(right)
  File "F:\Python\a\tem4.py", line 14, in visit
    yield from visit(right)
  File "F:\Python\a\tem4.py", line 12, in visit
    yield from visit(left)
  File "F:\Python\a\tem4.py", line 12, in visit
    yield from visit(left)
  File "F:\Python\a\tem4.py", line 7, in visit
    value, left, right = tree
ValueError: not enough values to unpack (expected 3, got 2)

The traceback gives the path from the root to the bad node. One could wrap the original visit(tree) call to reduce the traceback to the path: (root, right, right, left, left).

If the recursive calls are included in the try: clause, the error is recaught, relogged, and reraised at each level of the tree.

Bad tree: (9, None)
Bad tree: (8, (9, None), None)
Bad tree: (7, (8, (9, None), None), None)
Bad tree: (6, None, (7, (8, (9, None), None), None))
Bad tree: (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))), (6, None, (7, (8, (9, None), None), None)))
Traceback (most recent call last):
...  # same as before

The multiple logging reports are likely more noise than help. If one wants the path to the bad node, it might be easiest to wrap each recursive call in its own try: clause and raise a new ValueError at each level, with the contructed path so far.

Conclusion: if one is not using an exception for flow control (as may be done with IndexError, for instance) the presence and placements of try: statements depends on the error reporting one wants.

Solution 4

Up to Python 3.4, a generator function used to have to raise StopIteration exception when it is done. For the recursive case other exceptions (e.g. IndexError) are raised earlier than StopIteration, therefore we add it manually.

def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6, 3, 9, 1]):
    print(k)

---

def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis.pop(0)
    yield from recursive_generator(lis)

for k in recursive_generator([6, 3, 9, 1]):
    print(k)

Note that for loop will catch StopIteration exception. More about this here

Solution 5

The reason your recursive call only executes once is that you are essentially creating nested generators. That is, you are creating a new generator inside a generator each time you call the function recursive_generator recursively.

Try the following and you will see.

def recursive_generator(lis):
    yield lis[0]
    yield recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(type(k))

One simple solution, like others mention, is to use yield from.

View more solutions

Comments

[jpmc26]

I don't see a need for an else block on the try/except; it would be simpler to just move that code into the try block, wouldn't it?

[jpmc26]

Are you sure that a recursive generator can't just return normally when its done? Also, modifying your input in place is generally something you want to avoid.

[Terry Jan Reedy]

Simpler? Yes. Better? Not according to many experts, starting with GvR. python.org/dev/peps/pep-0008/#programming-recommendations "Additionally, for all try/except clauses, limit the try clause to the absolute minimum amount of code necessary. Again, this avoids masking bugs."

[Terry Jan Reedy]

@jpmc26 currently, yes. Starting with 3.6, explicitly raising StopIteration inside a generator function is a RuntimeError. Typically, just return. See python.org/dev/peps/pep-0479

[smci]

Actually since back in 3.5, explicitly raising StopIteration inside a generator function is deprecated cc: @TerryJanReedy. So Levon's answer is an old recommendation up to 3.4. Most of us never liked writing explicit StopIteration anyway, it was unnecessary.

[Terry Jan Reedy]

@jpmc26 See Edit 2 for a discussion of your comment.

[Michael Iyke]

Thank you very much. Been wondering all day why code refused to obey my orders

[Teepeemm]

For yield from, see docs.python.org/3/whatsnew/3.3.html#pep-380

[Teepeemm]

Is that else block indented correctly?

[Terry Jan Reedy]

@Teepeemm Yes, the else belongs to the try. It is executed if there is no exception. docs.python.org/3/reference/…

[Yuta73]

If lis: is the same as if len(lis)>0: ?

[Alec]

@Yuta73 yes, it is

[mVChr]

To simplify that verbose python.org doc explaining yield from, yield from g is essentially equivalent to for x in g: yield x