代码之家 › 专栏 › 技术社区 › nwhiting

简单PHP递归测试失败

recursion php

nwhiting · 技术社区 · 15 年前

我正在尝试一个基本的递归来创建基于输入数组值的多维数组。

递归的工作原理是检查一个值,我们称之为“递归”,以启动循环并查找另一个值,我们称之为“停止递归”以结束循环。

基本上取这个数组

array('One', 'Two', 'recursion', 'Three', 'Four', 'Five', 'stop_recursion', 'Six', 'Seven')

做这个阵列

array('One', 'Two', array('Three', 'Four', 'Five'), 'Six', 'Seven')

到目前为止,我的代码如下

function testRecrusion($array, $child = false)
{
    $return = array();

    foreach ($array as $key => $value) {
        if ($value == 'recursion') {
            unset($array[$key]);
            $new = testRecrusion($array, true);
            $array = $new['array'];
            $return[] = $new['return'];
        } else {
            if ($value == 'stop_recursion') {
                unset($array[$key]);
                if ($child) {
                    return array('return' => $return, 'array' => $array);
                }
            } else {
                unset($array[$key]);
                $return[] = $value;
            }
        }
    }

    return $return;
}

但其结果是

Array
(
    [0] => One
    [1] => Two
    [2] => Array
        (
            [0] => Three
            [1] => Four
            [2] => Five
        )

    [3] => Three
    [4] => Four
    [5] => Five
    [6] => Six
    [7] => Seven
)

我想真正的问题是……数组值是否会持续循环通过初始调用给出的第一个值,或者一旦返回新数组并设置它将循环通过该新数组。我知道答案基本上就在这里说,是的,它将继续旧的数组值,但这不应该工作,反之亦然?

如有任何帮助,我们将不胜感激:)

--------编辑-------------

我还可以补充一点,虽然我可以使用一个更简单的方法来执行这个操作,但是需要递归地检查这个操作,因为它将被移植到一个字符串解析器,这个解析器可以有无限多的子数组。

5 回复 | 直到 15 年前

Mark Byers 15 年前

当您返回到递归内部时,需要同时返回内部数组和索引,以便继续搜索元素,这样您就不会两次查看同一个元素。试试这个:

function testRecursionImpl($array, $i)
{
    $return = array();

    for (; $i < sizeof($array); ++$i) {
        if ($array[$i] == 'recursion') {
            $new = testRecursionImpl($array, $i + 1);
            $return[] = $new[0];
            $i = $new[1];
        } else if ($array[$i] == 'stop_recursion') {
            return array($return, $i);
        } else {
            $return[] = $array[$i];
        }
    }

    return array($return, $i);
}

function testRecursion($array)
{
    $result = testRecursionImpl($array, 0);
    return $result[0];
}

RaYell 15 年前

上面代码中的问题是,您正确地检测到什么时候应该递归地调用这个函数,但是一旦它完成运行,并且将结果附加到输出数组中,您只需选择下一个元素(这是递归调用将得到的第一个元素)并将其附加到输出数组中。您可能想做的是,当您检测到应该递归地运行函数时,应该跳过所有其他字符,直到找到停止字为止。( stop_recursion )显然,如果您允许多级递归,那么问题将变得更加困难,那么您甚至可能需要跳过一些停止字,因为它们可能来自不同级别的调用。

不过,我不知道你为什么想要这样的功能。也许你会解释一下你想达到什么样的目标。我很确定还有另一种更简单的方法。

James Black 15 年前

与其帮你做功课,我建议你先把这句话删掉:

foreach ($array as $key => $value) {

你应该通过你的数组,检查是否在数组的末尾,因为它不能是无限的,知道你什么时候完成。

mauris 15 年前

让我试试看

function testRecursion($arr){
    $return = array();
    $recurlevel = 0;
    foreach ($arr as $v) {
      if($v == 'stop_recursion'){
        $recurlevel--;
      }
      if($recurlevel == 0){
        if(isset($current)){
          $return[] = testRecursion($current);
          unset($current);
        }else{
          if($v != 'recursion'){
            $return[] = $v;
          }
        }
      }else{
        if(!isset($current)){
           $current = array();
        }
        $current[] = $v;
      }
      if($v == 'recursion'){
        $recurlevel++;
      }
    }

    return $return;
}

好的,做得很好。即使递归和停止递归嵌套在另一个递归中,这也会有所帮助。参见示例:

PHP:

<pre><?php

function testRecursion($arr){
    $return = array();
    $recurlevel = 0;
    foreach ($arr as $v) {
      if($v == 'stop_recursion'){
        $recurlevel--;
      }
      if($recurlevel == 0){
        if(isset($current)){
          $return[] = testRecursion($current);
          unset($current);
        }else{
        if($v != 'recursion'){
          $return[] = $v;
        }
        }
      }else{
        if(!isset($current)){
           $current = array();
        }
          $current[] = $v;
      }
      if($v == 'recursion'){
        $recurlevel++;
      }
    }

    return $return;
}

$a = array('One', 'Two', 'recursion', 'Three', 'recursion', 'Four' , 'stop_recursion', 'Five', 'stop_recursion', 'Six', 'Seven');
var_dump(testRecursion($a));

?>

浏览器输出:

array(5) {
  [0]=>
  string(3) "One"
  [1]=>
  string(3) "Two"
  [2]=>
  array(3) {
    [0]=>
    string(5) "Three"
    [1]=>
    array(1) {
      [0]=>
      string(4) "Four"
    }
    [2]=>
    string(4) "Five"
  }
  [3]=>
  string(3) "Six"
  [4]=>
  string(5) "Seven"
}

VolkerK 15 年前

既然您对递归解决方案的问题已经得到了解答…我可以提供一个基于堆栈的解决方案吗?

$x = array('a', 'b', 'recursion', 'cI', 'cII', 'cIII', 'recursion', 'cIV1', 'cIV2', 'cIV2', 'stop_recursion', 'stop_recursion', 'd', 'e');

$result = array();
$stack = array(&$result);
foreach($x as $e) {
  if ( 'recursion'===$e ) {
    array_unshift($stack, array());
    $stack[1][] = &$stack[0];
  }
  else if ( 'stop_recursion'===$e ) {
    array_shift($stack);
  }
  else {
    $stack[0][] = $e;
  }
}

var_dump($result);

印刷品

array(5) {
  [0]=>
  string(1) "a"
  [1]=>
  string(1) "b"
  [2]=>
  array(4) {
    [0]=>
    string(2) "cI"
    [1]=>
    string(3) "cII"
    [2]=>
    string(4) "cIII"
    [3]=>
    array(3) {
      [0]=>
      string(4) "cIV1"
      [1]=>
      string(4) "cIV2"
      [2]=>
      string(4) "cIV2"
    }
  }
  [3]=>
  string(3) "d"
  [4]=>
  string(5) "e"
}