[Tutor] How to find descendants recursively?

[Dave Angel]

On 06/16/2013 01:20 PM, Timo wrote:
> I have a datafile which is parsed by an external library, I'm having
> trouble creating a hierarchical structure of the data.
>
> This is what I got so far:
>
> items = get_items() # returns a generator
> for item in items:
>      print(item)
>      children = get_children(item) # also returns a generator
>      for child in children:
>          print("--", child)
>
> This is fine as it will get the children for each parent item. I can't seem
> to figure out how to go further and get the chidren of the children and so
> on.
>
I can't see any way of doing recursion without writing a function.  You 
can always fake it, but if you want the language's help, do it in a 
function.

We don't know your external library.  But if the effect is to produce a 
tree, where any node may have items as children, then recursion is the 
easiest way to process the whole tree.  Some assumptions are important:

The tree has reasonable max-depth, like less than 1000.  If it's 
somewhat larger, but has a known limit, you can probably just get away 
with telling Python to use a larger stacksize.  But if the depth could 
be arbitrarily large, say a million levels, then you need another 
approach than the language's recursion.

Second assumption is that no node appears more than once in the tree. 
For example, in a Unix directory tree, if a symlink points back up the 
tree, it can cause troubles.  Avoiding these troubles is not hard if you 
plan ahead, but it's easier if you know it cannot happen.

Assuming the tree is well-enough behaved then, we want to define a 
function, with a name, that will call itself.  Each time you descend 
into a  child node, you call the function recursively to process that 
childlist.

Now, eventually you'll probably want to make this recursive function a 
generator, so you can reuse it for other tree processing of the same 
kind of tree.  But that can wait.

First you have to decide how you can test the limit-condition.  For 
example, perhaps your unknown library returns Null from  the 
get_children() call if there are no children.  Or perhaps there's 
another call, like has_children() which returns a bool.  Without knowing 
that, it's hard to structure the rest of the function.  But roughly it 
looks like:

after the children= line, simply test your condition and call yourself 
with children as the argument.

     children = get_children(item)
     if children not is None:
         my_recursive_function(children)

You don't need or want to write a loop for child in children, since that 
same loop is already written (if item in items).



You pick your own better name for the function, based on what it does.

-- 
DaveA