Recursive generator

[Paul Hankin]

On Feb 12, 10:17 pm, Ben C <spams... at spam.eggs> wrote:
> On 2008-02-12, Paul Rubin <> wrote:
>
> > Paul Hankin <paul.han... at gmail.com> writes:
> >> def genDescendants(self):
> >>     return chain([self], *[child.genDescendants()
> >>         for child in self.children])
>
> > That is scary.  It generates an in-memory list the size of the
> > whole subtree, at every level.  Total memory consumption is maybe
> > even quadratic, depending on the tree shape, but even if it's
> > only linear, it's way ugly.
>
> This would probably be better (in terms of memory if not beauty):
>
>     def genDescendants(self):
>         return chain([self], *(child.genDescendants()
>             for child in self.children))

No, it's the same I think. When I wrote the original function, I
forgot that a generator using yield isn't the same as the same
function that returns an equivalent generator, because one is lazy and
the other isn't. To get the lazy behaviour back, you'd have to
write....

def genDescendants(self):
    for g in chain([self], *(child.genDescendants()
            for child in self.children)):
        yield g

But that's really ugly, so it looks like the simple version which
doesn't use itertools is the best.

--
Paul Hankin