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. — , Jun 06 '12 at 19:41
Check this. http://stackoverflow.com/a/10777501/1420642 It's for nested comments, but it's almost the same — Nicolás Torres, Jun 06 '12 at 19:41

score 3 · Answer 1 · answered Jun 06 '12 at 19:40

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 06 '12 at 19:40

Ruben

2,488
1
18
22

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 – pioSko Jun 06 '12 at 19:42
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. – Ruben Jun 06 '12 at 19:43

anubhava · Accepted Answer · 2012-06-06T20:52:57.003

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 06 '12 at 20:52

answered Jun 06 '12 at 19:59

anubhava

761,203
64
569
643

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. – pioSko Jun 06 '12 at 20:36
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 – anubhava Jun 06 '12 at 20:51
Thank you, anubhava! Working :) – pioSko Jun 07 '12 at 10:07

score 1 · Answer 3 · answered Jun 06 '12 at 19:55

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;
}

PHP Recursion not stopping

3 Answers3