Recursive function says it's doing one thing, actually does another?

Question

My problem: from an animal genealogy database, retrieve the descendants of a particular mother.

My solution, since I'm using mySQL, is to get all possible candidates and then use a recursive function in PHP.

Leaving aside the more important questions of whether the database model that I'm using is well designed, whether there's a more elegant way of retrieving the data, or whether the recursive function itself is particularly efficient, I'd like some insight into why the solution that I've come up with isn't quite working. As I echo the output at various places, it says that it's returning the correct children; yet the actual return doesn't correspond.

So, my sql simply returns all child IDs matched with their mothers IDs and then builds an array where the child is the key and the mother is the value. On the chance that the data had some weirdness, I decided to hard code an array with the exact results returned:

$aData = array("1"=>"20", "14"=>"12", "15"=>"14", "16"=>"10", "20"=>"13", "23"=>"20", "46"=>"20", "39"=>"12", "43"=>"13", "44"=>"13", "54"=>"1", "49"=>"1", "113"=>"46", "112"=>"54", "130"=>"15", "131"=>"43");

The recursive function:

// $targetMom is the mother whose descendants I want
// $targetChild is each possible candidate
// $childID is initially the same as $targetChild
function recurseTree($data, $childID, $targetMom, $row, $targetChild){
    $momID = isset($data[$childID]) ? $data[$childID] : -1 ; 
    //echo "row: " . $row . " id: " . $childID . " mom ID: " . $momID . " target: ". $targetMom . " final target: ". $targetChild . "<br />"; 

    if ($momID == $targetMom){
        echo $momID . "==" . $targetMom . "; returning target: ". $targetChild . "<br/><br/>";
        return $targetChild;                
    } else if ($row == sizeof($data)) { // reached the end of the data array - no more to check
        //echo "row: " . $row . "== size of array: " . sizeof($data) . "<br />";
        return -1;
    } else if ($momID == -1) { // this child doesn't have a mom defined
        //echo "momID == -1<br />";
        return -1;
    } else {
        //echo 'recursing<br/>';
        recurseTree($data, $momID, $targetMom, ++$row, $targetChild);
    }               
}

Finally, the calls to the recursive function, where for now I'm only interested in one particular mother with ID 12:

$children = array();
foreach( $aData as $k=> $v){
    $return = recurseTree($aData, $k, 12, 0, $k);
    if ($return != -1 && $return != null) {
        $children[] = $return;
    }
}

So, just looking at the output from the echo statement inside recurseTree(), it would appear that it's returning four values:

12==12; returning target: 14
12==12; returning target: 15
12==12; returning target: 39
12==12; returning target: 130

However, echoing the actual array that was built shows only two values pushed onto it:

Array
(
    [0] => 14
    [1] => 39
)

Feel free to post any tips on improving the code, but I'm most interested in why the echo statements don't match the elements in the $children array. Thanks!

I never heard functions speaking.... . Please check the title of you question. — hakre, Apr 25 '12 at 10:22

score 3 · Accepted Answer · answered Apr 25 '12 at 10:25

3

You need to:

return recurseTree($data, $momID, $targetMom, ++$row, $targetChild);

Otherwise the values obtained by inner iterations never make it back to the outer scope.

answered Apr 25 '12 at 10:25

DaveRandom

87,921
11
154
174

Bingo... thanks Dave; it's been a very long time since I had to design a recursive function, and it doesn't help that I'm rusty on PHP. – earachefl Apr 25 '12 at 10:29
I actually have done the exact same thing recently and spent two hours trying to work out why it wasn't working - I have done a lot of Node.js in the last few weeks and got complacent about scope inheritance... – DaveRandom Apr 25 '12 at 10:31

Recursive function says it's doing one thing, actually does another?

1 Answers1