Simple PHP Recursion Test Failing

Question

Hello,

I am attempting a basic recursion to create multi-dimensional arrays based on the values of an inputed array.

The recursion works by checking for a value we shall call it "recursion" to start the loop and looks for another value we'll call it "stop_recursion" to end.

Basically taking this array

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

And making this array

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

The code I have for it so far is as follows

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

But the output from that is

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

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

I guess the real question is...will an array values continuously loop through the first values given from the initial call or once the new array is returned and set will it loop through that new array. I know the answer is basically right here saying that yes it will continue the old array value, but shouldn't this work vice-versa?

Any help will be appreciated :)

------------ edit -------------------

I might as well add that while I can perform this action using a much simpler method, this needs to be recursively checked since this will be ported to a string parser that could have a infinite number of child arrays.

Answer 1

The problem you have in the code above is that you correctly detect when you should call this function recursively but once it finishes running and you append the results to output array you just pick next element (which is the first element that recursive call will get) and append it to output array. What you probably want to do is when you detect that you should run your function recursively you should skip all other characters until you find your stop word (stop_recursion). Obviously the problem will become harder if you allow multi-level recursion then you may need to even skip some stopwords because they could be from the different level call.

Still I don't know why you want such a feature. Maybe you would explain what are you trying to achieve. I'm pretty sure there's another, simpler way of doing it.

Answer 2

Rather than helping with your homework, I would suggest you start with getting rid of this line:

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

You should just pass in your array, and check for being at the end of the array, since it can't really be infinite, to know when you are done.

Answer 3

When you return inside the recursion, you need to return both the inner array and the index from which to continue searching for elements so that you don't look at the same element twice. Try this instead:

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

Answer 4

Let me give it a try

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

Alright nicely done. This will help even if the recursion and stop_recursion are nested in another. See example:

code.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));

?>

Browser output:

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

Answer 5

Since your question for the recursive solution has already been answered ...might I offer a stack-based solution?

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

prints

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