Amanda Amanda - 3 months ago 15
PHP Question

PHP recursive foreach unexpected behavior

Update:

I figured out what was causing the infinite loop and put in a check to make sure each node was only included in the path once. This now returns a multi-level array with the expected values. Any ideas on how to get this all in a single-level array?

Array
(
[0] => Array
(
[0] => 200
[1] => Array
(
[0] => Array
(
[0] => 109
)

[1] => 155
)

[2] => Array
(
[0] => Array
(
[0] => 164
)

[1] => 110
)

)

)


New code:

function buildPath($nodes,$src,$target,$pathSum,$elements=array(1))
{
$paths=array();
foreach($nodes[$src] as $dest=>$dist)
{
$e=$elements;
$sum=$pathSum+$dist;
if(!in_array($dest,$e))
{
if($dest==$target)
{
$paths[]=$sum;
}
else
{
$e[]=$dest;
$paths[]=buildPath($nodes,$dest,$target,$sum,$e);
}
}
}
return $paths;
}





Original Post

long time lurker, first time poster. I would consider myself intermediate level in php, and I'm starting to dive into recursive functions. I ran into some rather unexpected behavior, and I'm very confused.

function buildPath($nodes,$src,$target,$pathSum)
{
$paths=array();
foreach($nodes[$src] as $dest=>$dist)
{
$sum=$pathSum+$dist;
if($dest==$target)
{
$paths[]=$sum;
}
elseif($dest!=$target)
{
$paths[]=buildPath($nodes,$dest,$target,$sum);
}
}
return $paths;
}


When I call the function with:

$src=1
$target=4
$pathSum=0
$nodes= Array
(
[1] => Array
(
[4] => 200
[2] => 5
[3] => 10
)

[4] => Array
(
[1] => 200
[2] => 150
[3] => 100
)

[2] => Array
(
[1] => 5
[3] => 4
[4] => 150
)

[3] => Array
(
[1] => 10
[2] => 4
[4] => 100
)

)


it runs an infinite loop until it times out. I started echoing out variables at different times to try and debug. When I call:

function buildPath($nodes,$src,$target,$pathSum)
{
$paths=array();
foreach($nodes[$src] as $dest=>$dist)
{
$sum=$pathSum+$dist;
if($dest==$target)
{
$paths[]=$sum;
echo "$src->$dest, Target=$target, distance=$dist, sum=$sum. | ";
}
elseif($dest!=$target)
{
$paths[]=buildPath($nodes,$dest,$target,$sum);
echo "$src->$dest, elseif clause | ";
}
}
print_r($paths);
return $paths;
}


with the same inputs, I get the following output:

1->4, Target=4, distance=200, sum=200. | 1->4, Target=4, distance=200, sum=210. | 1->4, Target=4, distance=200, sum=220. | 1->4, Target=4, distance=200, sum=230. | 1->4, Target=4, distance=2, sum=240. | 1->4, Target=4, distance=200, sum=250. |


repeated until the script times out, incrementing sum by 10 each iteration. dumping $paths reveals that it is not appending anything to the $paths array, simply updating $paths[0] to the new sum.

What am I missing here? Am I just completely misunderstanding how recursion should work?

Answer

Simply put the $paths outside the function and use it within the function as a Global variable like below and you may test it out here:

    <?php

        $src        = 1;
        $target     = 4;
        $pathSum    = 0;
        $nodes      = [
            1=>[4=>200,    2=>5,   3=>10],
            4=>[1=>200,    2=>150, 3=>100],
            2=>[1=>5,      3=>4,   4=>150],
            3=>[1=>10,     2=>4,   4=>100],
        ];

        $paths  = array();    //<== OUTSIDE THE FUNCTION.... AS GLOBAL VARIABLE...

        var_dump( buildPath($nodes, $src, $target, $pathSum) );

        function buildPath($nodes, $src, $target, $pathSum, $elements=array(1)) {
            global $paths;
            foreach($nodes[$src] as $dest=>$dist){
                $e      = $elements;
                $sum    = $pathSum+$dist;

                if(!in_array($dest, $e))    {
                    if($dest == $target){
                        $paths[] = $sum;
                    }else{
                        // SIMPLY RECURSE & NOT BUILD $path HERE
                        $e[] = $dest;
                        buildPath($nodes, $dest, $target, $sum, $e);
                    }
                }
            }
            return $paths;
        }

        // THE var_dump ABOVE PRODUCES:::           
        array (size=5)
          0 => int 200
          1 => int 109
          2 => int 155
          3 => int 164
          4 => int 110
Comments