Check arrays for recursion

Question

What is the best way to check if an array is recursive in PHP ?

Given the following code:

<?php 
$myarray = array('test',123); 
$myarray[] = &$myarray; 
print_r($myarray); 
?> 

From the PHP Manual:

The print_r() will display RECURSION when it gets to the third element of the array.

There doesn't appear to be any other way to scan an array for recursive references, so if you need to check for them, you'll have to use print_r() with its second parameter to capture the output and look for the word RECURSION.

Is there more elegant way of checking ?

PS. This is how I check and get the recursive array keys using regex and print_r()

$pattern = '/\n            \[(\w+)\] => Array\s+\*RECURSION\*/';
preg_match_all($pattern, print_r($value, TRUE), $matches);
$recursiveKeys =  array_unique($matches[1]);

Thanks

Answer 1

It's always fun to try solving "impossible" problems!

Here's a function that will detect recursive arrays if the recursion happens at the top level:

function is_recursive(array &$array) {
    static $uniqueObject;
    if (!$uniqueObject) {
        $uniqueObject = new stdClass;
    }

    foreach ($array as &$item) {
        if (!is_array($item)) {
            continue;
        }

        $item[] = $uniqueObject;
        $isRecursive = end($array) === $uniqueObject;
        array_pop($item);
        if ($isRecursive) {
            return true;
        }
    }

    return false;
}

See it in action.

Detecting recursion at any level would obviously be more tricky, but I think we can agree that it seems doable.

Update

And here is the recursive (pun not intended but enjoyable nonetheless) solution that detects recursion at any level:

function is_recursive(array &$array, array &$alreadySeen = array()) {
    static $uniqueObject;
    if (!$uniqueObject) {
        $uniqueObject = new stdClass;
    }

    $alreadySeen[] = &$array;

    foreach ($array as &$item) {
        if (!is_array($item)) {
            continue;
        }

        $item[] = $uniqueObject;
        $recursionDetected = false;
        foreach ($alreadySeen as $candidate) {
            if (end($candidate) === $uniqueObject) {
                $recursionDetected = true;
                break;
            }
        }

        array_pop($item);

        if ($recursionDetected || is_recursive($item, $alreadySeen)) {
            return true;
        }
    }

    return false;
}

See it in action.

Of course this can also be written to work with iteration instead of recursion by keeping a stack manually, which would help in cases where a very large recursion level is a problem.

Answer 2

The following function is simpler[opinion] than the code in the accepted answer, and seems to work for any use case that I have been able to contrive. It also seems to be surprisingly fast, typically taking microseconds, though I have not done extensive benchmarking. If there is a problem with it, I would be grateful if somebody could point it out?

// returns TRUE iff the passed object or array contains
// a self-referencing object or array
function is_r($obj, &$visited=array())
  {
  $visited[] = $obj;
  foreach ($obj as $el)
    {
    if (is_object($el) || is_array($el))
      {
      if (in_array($el, $visited, TRUE))
        return TRUE;
      if (is_r($el, $visited))
        return TRUE;
      }
    }
  return FALSE;
  }