Recursive tree

How can i populate the array to return the tree when the function finishes?

[asantos]

Hi, i made this function navbar():

function navbar($id_seccion_padre=0) {
global $cnn;
$sql = 'SELECT * FROM seccion WHERE id_seccion_padre='.$id_seccion_padre;
$rs = &$cnn->Execute($sql);
while(!$rs->EOF) {
$array[] = $id;
navbar($rs->fields['id_seccion']);
$rs->MoveNext();
}
return $array;
}

$tree = navbar();
print_r($tree);

It must return a website's section tree structure. Each section has an id_section_parent, and there are 'n' levels. The function is only returning me the first section value:
Array ( [0] => )

But i need to populate the array and then return it. Any ideas?

[siMKin]

Recursive functions are always a pain in the *ss.
My advice is to first write down what you want it to do in 'pseudocode [en.wikipedia.org]' and then transform that into working php code.
And to do that succesfully, first determine how you would like the output/result of your code to be (which in turn depends on what you want to do with it).

If you have difficulties writting the pseudo code, let me know, i could give you an example. But for that you'll need to determine how you want the output first.

[ergophobe]

Recursive functions are always a pain in the *ss.

Don't say that on a Scheme [swiss.ai.mit.edu] forum! Scheme is one of the most powerful languages going and used a lot in the AI community because of how fast you can do complex tasks. Yet it has no looping structures and uses recursion instead for all iteration.

Recursion is often an elegant and efficient way to solve a problem. There are many many tasks that can be done in a few lines with recursion that are cumbersome or impractical or downright impossible using nested loops. One of those things is building and traversing tree structures. How do you build an arbitrary-depth tree without recursion?

Just make absolutely sure that you have an end condition that prevents infinite recursion, which will eventually eat up all the memory and brign down your script, process or computer.

Try to make the recursion tail-recursive if possible. In other words, if at all possible, pass a parameter that accumulates results so that you don't have to recurse all the way back out to get your result. This will be much more efficient both in terms of processor steps and especially in terms of memory usage.

I don't think you can make your function tail-recursive because you have recursion inside a loop, so it needs t return the result of the recursion before it can go on to the next iteration of the loop. If your tree gets deep, this is going to get very costly.

[siMKin]

Recursive functions are always a pain in the *ss.

Don't say that on a Scheme forum! Scheme is one of the most powerful languages going and used a lot in the AI community because of how fast you can do complex tasks. Yet it has no looping structures and uses recursion instead for all iteration.

I didn't mean to say recursion is bad. Not at all! - i love recursion (when done properly). And it is indeed very powerfull.
I was just sympathizing with the TS - still remembering when i started with recursion. The concept is, i think, a bit more difficult to grasp than other things in PHP (or any other programming language). Well, maybe not difficult to grasp, but it's one of those things that always take a bit more time and thinking. That's what i meant with a pain in the ass.

Try to make the recursion tail-recursive if possible. In other words, if at all possible, pass a parameter that accumulates results so that you don't have to recurse all the way back out to get your result. This will be much more efficient both in terms of processor steps and especially in terms of memory usage.

I don't think you can make your function tail-recursive because you have recursion inside a loop, so it needs t return the result of the recursion before it can go on to the next iteration of the loop. If your tree gets deep, this is going to get very costly.

It won't get any more costly than other recursive functions. It doesn't need to anyways. It's just about creating a multi-dimensional array. The while loop of one iteration returns a flat array and where needed that flat array holds the array of another iteration. That way you can keep adding the returned result to the output-array you're working with. No need to recurse back.

The only thing that's gonna be a bit costly are the amount of database queries you'll need to run. But there is no way around that.

But as i said before, the first step would be to determine how you (the TS) want your output. You can't start without having that clear

[asantos]

Thanks for the replies.
This is the panorama:

I need a way to hold the values inside a multi-array. So if this is the data:

Start [1]
--About us [2]
----Mision [5]
----Vision [6]
--Employees [3]
----CV [7]
----Photos [8]
--Projects [4]
----Construction [9]
----Resources [10]

This must be the returned array for the function:
$arr = array(
[1]['t']=>'Start'
[1]['c']=>array(array([2]['t']=>'About us'...)
[...etc...]
);

t = title
c = children

I dont know if i explained myself very good, i hope you can help. Thanks.

[ergophobe]

Let's start by going back to the OP's problem, namely he doesn't do anything with the result, so it isn't filling the array. The results from the recursive call are returned, but not assigned.

What he needs to do is assign is something like this (untested)

function navbar($id_seccion_padre=0) { 
  global $cnn; 
  $sql = 'SELECT * FROM seccion WHERE id_seccion_padre='.$id_seccion_padre; 
  $rs = &$cnn->Execute($sql); 
  while(!$rs->EOF) {
    $tree[$rs->fields['id_seccion']]['name'] = $rs->fields['name_seccion]'; 
    $children = navbar($rs->fields['id_seccion']); 
    if (count($children)) { 
      $tree[$rs->fields['id_seccion']]['children'] = $children; 
    } 
    $rs->MoveNext(); 
  } 
  return $tree; 
} 

This assumes that
- category 0 does not actually exist, but is the "pseudo parent" of the top categories so the first time through it grabs the top catgories who have a parent id of 0 in the DB

- ADODB returns EOF = true if the result set is zero. If that's not the case, there must be some sort of method or property for the number of rows returned. In that case, before entering the while loop, you would want to test for results and then exit if the number of rows is zero.

Starting within the while loop, what were doing is

// Set the category name
$tree[$rs->fields['id_seccion']]['name'] = $rs->fields['name_seccion]';

// Grab the children
$children = navbar($rs->fields['id_seccion']);

// Did it return any children? If yes, add them to the tree.
if (count($children)) {
$tree[$rs->fields['id_seccion']]['children'] = $children;
}

Then return the tree.

[asantos]

I just readed the algorithm, it seems to work pretty good! I'll test it on my server and get back to this forum asap. Thanks!