Question

I know there s an easy way of doing this, but my recursion abilities are out of practice. Given a database table that has three fields:

id
label
child_id

I should be able to put together a recursive function that will give output like this:

child (input of program)
  parent1
  parent2
    grandparent1
      great-grandparent1
    grandparent2
    grandparent3
  parent3
    grandparent4
    grandparent5

I know it should be easy, but I can t get my mind to go through the mental gymnastics to make it work. Also, is this a good thing to do? Seems like I might end up leaving open quite a few database connections.

I think this is the part making it difficult for me. I m starting with a child_id, and working my way up. And a child can have many parents. So, the output would be the child id at the root of the tree and then it s parents and grandparents for each branch. The more I think about it, it s just the traditional one parent, many grandparents formula, except for semantics. I could just be over thinking it.

The table would look something like this:

table parents

id    child_id    label
 1     NULL       child
 2     1          parent1
 3     1          parent2
 4     1          parent3
 5     3          grandparent1
 6     3          grandparent2
 7     3          grandparent3
 8     5          great-grandparent1
 9     4          grandparent4
10     4          grandparent5

Answer 1

You could try this way

sub getChildren {
  my $id = shift;
  my $depth = shift;
  my $sql = qq/SELECT id,label,child_id FROM table WHERE id=?/;
  my $sth = $db->prepare($sql);
  my $sth->execute($id);
  while(my ($id,$label,$child_id)=$sth->fetchrow_array) {
    print " "x$depth,$label;
    getChildren($child_id,$depth++);
 }
}
getChildren($id);

Answer 2

I actually explained a quite similar problem in my blog, Implementing a depth first search in a PostgreSQL stored procedure, and my way of solving this using perl.

If your database doesn t support stored procedures you can do the same thing client-side, but you need to fetch the entire table first and do it in memory.

You could of course do it recursively and fetch each entry as you go along, but it will not scale because of the SQL statement overhead (except maybe on SQLite). If performance is not a problem this must be by far the easiest solution.

友情链接