# [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?

Yes.

>>> 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()
5
>>> it.next()
4
>>> it.next()
3
>>> it.next()
2
>>> it.next()
1
>>> it.next()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration

> 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 "<",
child.__iter__()
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
iterator.

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:

http://docs.python.org/library/stdtypes.html#iterator-types

> 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
```