2

不确定我在使用这个递归函数时做错了什么。我有一个包含网站树的数组，我正在寻找的页面可以无限​​深。该功能会遍历所有可能性，但有时在找到正确的“页面”时不会停止。

数组

$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()),
);

递归函数

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 = recurse(3);
print_r($test);

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

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

最后的测试输出：

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
(
)
4

3 回答 3

3

它返回但在其他递归框架中继续。例如，调用：1 -> 2 -> 3 -> 4。从 4 返回但 3 (1 -> 2 -> 3) 继续执行循环。

于 2012-06-06T19:40:51.877 回答
2

这是一个稍微修改的递归函数，可以解决您遇到的问题：

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

基本上，它声明了一个静态变量$_tmp，该变量仅初始化一次，然后检查仅在$_tmp 为空时才处理循环，以确保在找到针头后停止进一步处理。

Online working demo of above code

于 2012-06-06T19:59:41.493 回答
1

只有当您在您所在的级别上找不到任何东西时，您才能进入阵列，如下所示：

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;
}
于 2012-06-06T19:55:49.060 回答