detecting infinite array recursion in PHP?

Question

i've just reworked my recursion detection algorithm in my pet project dump_r()

https://github.com/leeoniya/dump_r.php

detecting object recursion is not too difficult - you use spl_object_hash() to get the unique internal id of the object instance, store it in a dict and compare against it while dumping other nodes.

for array recursion detection, i'm a bit puzzled, i have not found anything helpful. php itself is able to identify recursion, though it seems to do it one cycle too late. EDIT: nvm, it occurs where it needs to :)

$arr = array();
$arr[] = array(&$arr);
print_r($arr);

does it have to resort to keeping track of everything in the recursion stack and do shallow comparisons against every other array element?

any help would be appreciated,
thanks!

• Basic: Not an answer to your quesiton but I've seen solutions that test print_r($var, true) for the string indicating recursion. This is about as nasty as you can get but works... See here for a decent compromise.
• Basic: I've deleted/edited my comment to contain a link to an example but I agree, it stinks

Answer 1

Because of PHP's call-by-value mechanism, the only solution I see here is to iterate the array by reference, and set an arbitrary value in it, which you later check if it exists to find out if you were there before:

function iterate_array(&$arr){
 if(!is_array($arr)){
 print $arr;
 return;
 }
 // if this key is present, it means you already walked this array
 if(isset($arr['__been_here'])){
 print 'RECURSION';
 return;
 }
 $arr['__been_here'] = true;
 foreach($arr as $key => &$value){
 // print your values here, or do your stuff
 if($key !== '__been_here'){
 if(is_array($value)){
 iterate_array($value);
 }
 print $value;
 }
 }
 // you need to unset it when done because you're working with a reference...
 unset($arr['__been_here']);
}

You could wrap this function into another function that accepts values instead of references, but then you would get the RECURSION notice from the 2nd level on. I think print_r does the same too.

• leeoniya: this is the solution i was hoping for - simple and awesome.

Answer 2

Someone will correct me if I am wrong, but PHP is actually detecting recursion at the right moment. Your assignation simply creates the additional cycle. The example should be:

$arr = array();
$arr = array(&$arr);

Which will result in

array(1) { [0]=> &array(1) { [0]=> *RECURSION* } } 

As expected.

---

Well, I got a bit curious myself how to detect recursion and I started to Google. I found this article http://noteslog.com/post/detecting-recursive-dependencies-in-php-composite-values/ and this solution:

function hasRecursiveDependency($value)
{
 //if PHP detects recursion in a $value, then a printed $value 
 //will contain at least one match for the pattern /\*RECURSION\*/
 $printed = print_r($value, true);
 $recursionMetaUser = preg_match_all('@\*RECURSION\*@', $printed, $matches);
 if ($recursionMetaUser == 0)
 {
 return false;
 }
 //if PHP detects recursion in a $value, then a serialized $value 
 //will contain matches for the pattern /\*RECURSION\*/ never because
 //of metadata of the serialized $value, but only because of user data
 $serialized = serialize($value);
 $recursionUser = preg_match_all('@\*RECURSION\*@', $serialized, $matches);
 //all the matches that are user data instead of metadata of the 
 //printed $value must be ignored
 $result = $recursionMetaUser > $recursionUser;
 return $result;
}

• leeoniya: you're right. it's not late. but i still need a way to do this outside the native function.
• leeoniya: well, this solution is not exactly what i was hoping for since it is hugely taxing on large structures and relies on an internal uncontrollable-depth print_r() or serialize, which is part of the reason i started the project to begin with, heh, but phpsadness.com :(

Answer 3

Modernized version based on the answer given in 2012:

function isRecursive(array &$arr) : bool
{
 static $MARKER = '__RECURSIVE_MARKER__';
 
 try {
 if ( isset($arr[$MARKER]) ) {
 // recursion detected
 return true;
 } else {
 $arr[$MARKER] = true;
 foreach ($arr as $key => &$val) {
 if ( is_array($val) && isRecursive($val) ) {
 return true;
 }
 }
 }
 // If we got here, no recursion was found in this array or its children
 return false;
 } finally {
 // ensure we undo changes to the array
 unset($arr[$MARKER]);
 }
}

• Jeremy Caney: Thank you for contributing to the Stack Overflow community. This may be a correct answer, but it’d be really useful to provide additional explanation of your code so developers can understand your reasoning. This is especially useful for new developers who aren’t as familiar with the syntax or struggling to understand the concepts. Would you kindly edit your answer to include additional details for the benefit of the community?