Recursive function returning a list

malkarouri at gmail.com malkarouri at gmail.com
Wed Jul 19 16:28:45 EDT 2006


Bruno Desthuilliers wrote:
> malkarouri at gmail.com wrote:
[...]
> > Sorry, but I kinda agree with Boris here.
>
> On what ?

On the argument that you are (implicitly?) disagreeing with him on,
obviously. That the OP problem is not definitely the default values
question. As you say:

> >>If the OP has other reasons to want to use an accumulator based solution
> >>- which we don't know - then the possibility to use a default value is
> >>important.

My emphasis is on "we don't know".

>
> > Not that I am anybody here,
> > really.
>
> Err... Are you you at least ?-)
>

I am. Thanks for your concern:)

> Note that the generator-based solution doesn't return a list. (And yes,
> I know, it's just a matter of wrapping the call to obj.genAllChildrens()
> in a list constructor).

And you can do the wrapping in a function that returns a list, to be
more pedantic. And yes, I know you know.

>
> > I don't think there is actually a FAQ
> > saying you must use the accumulator solution.
>
> Did I say so ? The FAQ I mention is about default values evaluation, and
> it's the problem the OP was facing. Please re-read my post more carefully.
>

Actually, I have read your post right first time. And I do know you
didn't say that (a FAQ for accumulators). I raised it just in case.
What I don't agree with is that it is not the problem the OP was
facing. The discussion was: is the real problem the default values
problem, which he already got a solution for. Or was the real problem
the list returning recursion problem, for which he (or subsequent
google searchers, who are more likely to come to this thread after
searching for "Recursive function returning a list") may benefit from a
generator approach.

> > Actually, the accumulator based solution kind of comes to me
> > automatically as standard in any programming language, and I believe
> > that this was established as standard in python, _before_ the
> > introduction of generators.
>
> FWIW, you don't need to pass an accumulator around to solve this problem:
>
>     def getAllChildren(self):
>         children = []
>         if self.children:
>             children.extend(self.children)
>             for child in self.children:
>                 children.extend(child.getAllChildren())
>         return children

Thanks for the function, though I regard it as kind of trivial for the
level of discussion that we are having now. The problem solved by the
accumulator is _not_ the building of a list recursively. It is doing so
efficiently. Which is definitely not done by creating multiple
temporary lists just to add them. I am sure you know the theory. More
of relevance is that the generator based solution has also the same
efficiency, so they are both better than the trivial solution.
You have a point though. Your function is a solution. Just I don't
regard it as the preferred solution for the problem as I see it. YMMV.

To recap, the OP (and subsequent google searchers, if they pass by) has
now the preferred solution according to you. To my satisfaction, they
will also read the other solution, which looks more pythonic to me. As
I see it, any additional discussion now suffers from diminishing
returns.

Regards,
k




More information about the Python-list mailing list