[Tutor] recursive generator

Steven D'Aprano steve at pearwood.info
Sun Mar 7 14:27:40 CET 2010

On Sun, 7 Mar 2010 11:58:05 pm spir wrote:
> Hello,
> Is it possible at all to have a recursive generator? 


>>> def recursive_generator(n):
...     if n == 0:
...         return
...     yield n
...     for i in recursive_generator(n-1):
...         yield i
>>> it = recursive_generator(5)
>>> it.next()
>>> it.next()
>>> it.next()
>>> it.next()
>>> it.next()
>>> it.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>

> I think at a 
> iterator for a recursive data structure (here, a trie). The following
> code does not work: it only yields a single value. Like if
> child.__iter__() were never called.
>     def __iter__(self):
>         ''' Iteration on (key,value) pairs. '''
>         print '*',
>         if self.holdsEntry:
>             yield (self.key,self.value)
>         for child in self.children:
>             print "<",
>             child.__iter__()
>             print ">",
>         raise StopIteration

__iter__ should be an ordinary function, not a generator. Something like 
this should work:

# Untested.
    def __iter__(self):
        ''' Iteration on (key,value) pairs. '''
        def inner():
            print '*',  # Side effects bad...
            if self.holdsEntry:
                yield (self.key,self.value)
            for child in self.children:
                print "<",
                print ">",
            raise StopIteration
        return inner()

This means that your class won't *itself* be an iterator, but calling 
iter() on it will return a generator object, which of course is an 

If you want to make your class an iterator itself, then you need to 
follow the iterator protocol. __iter__ must return the instance itself, 
and next must return (not yield) the next iteration.

class MyIterator(object):
    def __init__(self, n):
        self.value = n
    def next(self):
        if self.value == 0:
            raise StopIteration
        self.value //= 2
        return self.value
    def __iter__(self):
        return self

See the discussion in the docs about the iterator protocol:


> Why is no child.__iter__() executed at all? I imagine this can be
> caused by the special feature of a generator recording current
> execution point.

That's exactly what generators do: when they reach a yield, execution is 
halted, but the state of the generator is remembered. Then when you 
call the next() method, execution resumes.

> (But then, is it at all possible to have a call in a 
> generator? Or does the issue only appear whan the callee is a 
> generator itself?) Else, the must be an obvious error in my code.

I don't understand what you mean.

Steven D'Aprano

More information about the Tutor mailing list