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?

Answer 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.

Answer 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!