recursion function in php not working as expected

Question

private function find_children ($parent_id, $children, &$result) { foreach ($children as $c) { if ($c->parent_comment_id == $parent_id) { $result[] = $c; $this->find_children($c->id, $children, $result); } } return; }

The above function is supposed to take a starting parent id and recursively go through an array of children nodes (really just an object with a unique id and a parent id) sorting them so that each node comes directly after it's parent (see below for sample data).

But for some reason, the function doesn't execute as I expect. I have the following data for testing.

id: 1 pid: 0 (the initial parent which is not in the children array passed to func. problem?) id: 2 pid: 1 id: 3 pid: 2 id: 4 pid: 1 id: 5 pid: 3 id: 6 pid: 5 id: 7 pid: 4 id: 8 pid: 3

and want the following array returned: 1, 4, 7, 2, 3, 8, 5, 6

But instead, I get: 1, 2, 3, 5, 6

which, while they're in the right order, a few are missing.

I have not had the need to do recursion in many years, so likely I am missing something obvious, although not so obvious to myself.

In case anyone is wondering, or if it matters, I'm trying to build a q&a commenting system where every post can have multiple replies.

Thus:

initial post -reply to initial post #1 --reply to reply -reply to initial post #2 -- reply to above --- reply to above --reply to #2

You loop through $children but then you loop through the same $children array on each subsequent recursed call. Do you want to pass a different value of children to the recursed function? — PP.
– PP., Commented Nov 19, 2009 at 18:29

Cody Gray · Accepted Answer · 2022-05-22 08:00:27Z

1

I think you're looking for something like a Nested Set Tree. It should do what you want.

edited May 22, 2022 at 8:00

Cody Gray♦

246k53 gold badges512 silver badges591 bronze badges

answered Nov 19, 2009 at 18:49

Carlos Lima

4,17031 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

allanmc · Accepted Answer · 2009-11-19 20:16:22Z

When i run your function on the data you listed, i do get the order you described, but i'm not missing any items:

id: 1, pid:0 id: 2, pid:1 id: 3, pid:2 id: 5, pid:3 id: 6, pid:5 id: 8, pid:3 id: 4, pid:1 id: 7, pid:4

And this result is actually the tree structure you want, just ordered ascending by the id's. If you order your chhildren-array descending by the id's, then you actually do get the output you request:

id: 1, pid:0 id: 4, pid:1 id: 7, pid:4 id: 2, pid:1 id: 3, pid:2 id: 8, pid:3 id: 5, pid:3 id: 6, pid:5

You should make sure you get the data in descending order from your DB. For this non-DB test case, i fixed it by using the following before calling find_children():

function revCmpObjects($a, $b) { //Just a basic descending ordering by the id if ($a->id == $b->id) { return 0; } return ($a->id > $b->id) ? -1 : 1; } usort($children, 'revCmpObjects'); //The actual sorting

Here is how I think the nodes should be displayed (if I could get the function working) id 1, pid 0 - id 2, pid 1 -- id 3, pid 2 --- id 5, pid 3 ---- id 6, pid 5 - id 4, pid 1 -- id 7, pid 4 notice how, while node 4 is second from the last in my list and node 2 and all of its children are above it.
You forgot id:9 in your list, but if you add that between id:3 and id:5, then you have the first output i posted. So i think you need to clearify some more. Is it actually just the tree depth you want added to each node?
But it is different. You have: 1, 4, 7, 2, 3, 8, 5, 6 While I have: 1, 2, 3, 8, 5, 6, 4, 7 which, now that I look at it, is really only due to us ordering the id's different (low vs. high values)

Collectives™ on Stack Overflow

recursion function in php not working as expected

2 Answers 2

Comments

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Related