[Tutor] recursive generator

[Steven D'Aprano]

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