Detect infinite recursion?

Question

Suppose I have a function that bypasses an array ...

flatten([a, b, c, d, [e, f, g, [h, i, j, k], l], m, n, o, p]) >> [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] 

Flatten will scan the code and for each array it encounters, it will recursively enter this array and return values, so you have a flat array.

This works until we have an array, for example:

 a = []; a[0] = a; 

This obviously creates infinite recursion:

 Array[1] 0: Array[1] 0: Array[1] 0: Array[1] 0: Array[1] 0: Array[1] 0: Array[1] ... 

How can I detect this behavior without modifying the array so the function can handle it?

Answer 1

If recursion detection is a must, you will have to swap memory space for it: create an array of objects that you parse (parameters that you send recursively) and check each new parameter for it. If you have already taken it apart, return immediately.

Answer 2

You need to save the array of the array visited in the flatten() function, and check their existence there until you curse it. You will need to pass the list of visited items as the second parameter to recurse , though.

 function recurse(ar, visited) { visited = visited || []; function isVisited(obj) { for (var i=0;i<visited.length;i++) { if (visited[i] == obj) { return true; } } visted.push(obj); // but we've visited it now return false; } // blah blah blah, do your thing... check isVisted[i] } 

It will become expensive to check if your array is enough so that you can trick and set an attribute for each array you visit and check it (but then, of course, you modify the array (but not abruptly)).

 function recurse(ar) { function isVisited(obj) { var key = 'visited'; var visited = obj.hasOwnProperty(key); obj[key] = true; // but we've visited it now return visited; } // blah blah blah, do your thing... check isVisted[i] } 

Answer 3

A convenient way to track arrays that have already been visited is to add a “flat” property to them, possibly setting some unique value for it for each operation. No point interferes with a separate map when each array is already a completely good object.

Answer 4

Another, more dirty way (but good for minimal fuss) is to simply use a JSON encoder:

 var is_recursive = false; try { JSON.stringify(my_recursive_object); } catch (e) { if (e.name = 'TypeError') is_recursive = true; else throw e; } 

I found this question, trying to find a better answer, though, although this may help someone wish a nice hack; -)

Answer 5

In the real world, step 1 is to find the intruder who handed you the object for self-regulation and hit them with a stick.

The problem is solved, however, eliminating them as self-references in place. Rotate them in a copy. Array.slice returns parts of arrays (including full copies) without changing the original.

 if(thisElement.constructor.prototype.slice){ //is it an array thisElement = thisElement.slice(0); //now it a new but identical array } 

Note that this applies only to the main array. Links to internal arrays will still need to be changed, since the copied link still points to the same thing.

Also, if you can make assumptions about characters that definitely won't be present, you can find slice / join to be very useful.