PHP recursive foreach unexpected behavior

Question

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?

$paths[]=buildPath($nodes,$dest,$n,$sum); How did the $n magically get invited to the party? — Poiz
– Poiz, Commented Aug 16, 2016 at 0:49
Sorry, replace $n with $target. I was trying to clarify the code, and must have copied before I finished all the replacements. My code calls $paths[]=buildPath($nodes,$dest,$target,$sum) — Amanda
– Amanda, Commented Aug 16, 2016 at 0:57

Poiz · Accepted Answer · 2016-08-16 01:55:57Z

2

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

answered Aug 16, 2016 at 1:55

Poiz

7,5872 gold badges17 silver badges17 bronze badges

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

1 Comment

Amanda Over a year ago

Great, this works, thanks! Marking as the answer since it works and is elegant. I did manage to solve it another way, instead of making $paths global, in my "else" block I used $paths=array_merge($paths,buildPath($nodes,$dest,$target,$sum,$e);

Amanda · Accepted Answer · 2016-08-16 02:10:48Z

Managed to solve it like this:

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=array_merge($paths,buildPath($nodes,$dest,$target,$sum,$e));
                    }
                }
            }
            return $paths;
        }

Arup Garai · Accepted Answer · 2016-08-16 00:36:55Z

1

Can you please change and check from

 elseif($dest!=$target)
        {
            $paths[]=buildPath($nodes,$dest,$n,$sum);
        }

To

 elseif($dest<=$target)
        {
            $paths[]=buildPath($nodes,$dest,$n,$sum);
        }

answered Aug 16, 2016 at 0:36

Arup Garai

1491 silver badge7 bronze badges

1 Comment

Amanda Over a year ago

That doesn't infinitely loop anymore, but not what I want. That was originally an else clause, but I changed it to elseif while troubleshooting. And still seeing unexpected results. It's only updating $paths[0] instead of appending another element to the array.

Collectives™ on Stack Overflow

PHP recursive foreach unexpected behavior

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related