PHP Recursion not stopping

Question

Not sure what I'm doing wrong with this recursion function. I have an array with a tree of a website and a page I'm looking for can be infinitely deep. The function goes through all possibilities but sometimes doesn't stop when it finds the right "page".

The array

$haystack = array(
    array("id" => 1,"parent" => 0,"route" => "home","children" => array()),
    array("id" => 2,"parent" => 0,"route" => "news","children" => array()),
    array("id" => 3,"parent" => 0,"route" => "photography","children" => array(
                array("id" => 6,"parent" => 3,"route" => "photography/portraits","children" => array()),
                array("id" => 7,"parent" => 3,"route" => "photography/countries","children" => array()),
                array("id" => 8,"parent" => 3,"route" => "photography/landscapes","children" => array(
                                array("id" => 9,"parent" => 8,"route" => "photography/landscapes/city","children" => array()),
                                array("id" => 10,"parent" => 8,"route" => "photography/landscapes/wilderness","children" => array())
                            )
                )
        )
    ),
    array("id" => 4,"parent" => 0,"route" => "about","children" => array()),
    array("id" => 5,"parent" => 0,"route" => "contact","children" => array()),
);

The recursion function

function recurse($needle = -1, $haystack = NULL){
    $_tmp = array();

    foreach($haystack as $key => $item)
    {
        echo $needle ." === ". $item["id"] . "<br/>";

        if((string)$item["id"] === (string)$needle){
            echo "Found: " . $needle . "<br/><br/>";
            $_tmp = $item;
            break;
            //return $item;   <-- this doesn't work either
        } else {
            $_tmp = recurse($needle, $item["children"]);
        }
    }
    return $_tmp;
}

Test cases:

$test = recurse(3);
print_r($test);

$test = recurse(7);
print_r($test);

$test = recurse(9);
print_r($test);

Last test outputs:

9 === 1
9 === 2
9 === 4
9 === 7
9 === 8
9 === 11
9 === 12
9 === 13
9 === 14
9 === 15
9 === 3
9 === 9
Found: 9  <-- should stop here, but continues

9 === 5
9 === 6
Array
(
)

The question title isn't supposed to be funny, but I keep reading it over and over and laughing. — user895378
– user895378, Commented Jun 6, 2012 at 19:41
Check this. stackoverflow.com/a/10777501/1420642 It's for nested comments, but it's almost the same — Nicolás Torres
– Nicolás Torres, Commented Jun 6, 2012 at 19:41

Ruben · Accepted Answer · 2012-06-06 19:40:51Z

3

It returns but continues in other recursion frame. For example, calls: 1 -> 2 -> 3 -> 4. Return from 4 but 3 (1 -> 2 -> 3) continues to execute loop.

answered Jun 6, 2012 at 19:40

Ruben

2,5782 gold badges19 silver badges22 bronze badges

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

2 Comments

pioSko Over a year ago

Yes, I know, but I thought return was supposed to stop it. I tried "break 2" but I get an error. I wan't the function just to stop everything :P

Ruben Over a year ago

It is not good practice, but you can pass some boolean variable initially set to false by reference and set it to true before break. Before start of loop check it's value and return if it is true.

anubhava · Accepted Answer · 2012-06-06 20:52:57Z

2

Here is a slightly modified recurse function that fixes the problem you have:

 function recurse($needle = -1, $haystack = NULL){
    static $_tmp = array();

    if (count($_tmp) == 0 && $haystack != NULL && count($haystack) > 0) {
       foreach($haystack as $key => $item) {
          if (count($_tmp) == 0) {
              echo $needle ." === ". $item["id"] . "<br/>\n";

              if((string)$item["id"] === (string)$needle){
                  echo "Found: " . $needle . "<br/>\n";
                  $_tmp = $item;
                  break;
              } elseif (!empty($item["children"])) {
                  echo "calling ". $item["id"]. ".children <br/>\n";
                  $_tmp = recurse($needle, $item["children"]);
              }
          }
       }
    }
    return $_tmp;
}

Basically it declares a static variable $_tmp that gets initialized only once and and then a check to process the loop only if $_tmp is empty makes sure to stop further processing once needle has been found.

Online working demo of above code

edited Jun 6, 2012 at 20:52

answered Jun 6, 2012 at 19:59

anubhava

790k67 gold badges603 silver badges671 bronze badges

3 Comments

pioSko Over a year ago

I'm getting the value back, but is there a way to stop all processes? Your test output shows it continues recursion after it has found the needle. If ever I have a huge array, 1000 items or so, there's no point for it to continue if I'm looking for something in, say, the first 10. Also, if I could stop the process at that point then I would have the value returned anyway.

anubhava Over a year ago

You can make it more efficient by another check of static variable's size inside the loop as in my last edit. See demo here: g ideone.com/WXtNB

pioSko Over a year ago

Thank you, anubhava! Working :)

DaneoShiga · Accepted Answer · 2012-06-06 19:55:49Z

1

You could go down the array only if you don't find anything on the level you are, something like this:

function recurse($needle = -1, $haystack = NULL){
    $_tmp = array();

    foreach($haystack as $key => $item)
    {   
        echo $needle ." === ". $item["id"] . "<br/>";

        if((string)$item["id"] === (string)$needle){
            echo "Found: " . $needle . "<br/><br/>";
            $_tmp = $item;
            break;
            //return $item;   <-- this doesn't work either
        }   
    }   
    if (empty($_tmp))
        foreach($haystack as $key => $item)
        {   
            $_tmp = recurse($needle, $item["children"]);
        }   

    return $_tmp;
}

answered Jun 6, 2012 at 19:55

DaneoShiga

1,0279 silver badges16 bronze badges

Collectives™ on Stack Overflow

PHP Recursion not stopping

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related