Detect infinite recursion?

Question

Lets assume I have a function that crawls over 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 would crawl over the code and for each array encountered would recursively enter into that array and return the values such that you have a flat array.

This works until we have an array such as:

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 modifiying the array such that the function can deal with this?

Can we maintain what we have crawled, and if we already have crawled that array, then we are in the situation described above ... — Nitin Midha, Mar 08 '12 at 15:20
Check out [this post](http://stackoverflow.com/a/9386208/989121). It basically shows how to write a function decorator that limits the recursion depth. — georg, Mar 08 '12 at 15:34

score 6 · Answer 1 · answered Mar 08 '12 at 15:22

6

If detecting recursion is a requirement, you're going to have to trade memory space for it: create an array of objects you parsed (the parameters you send recursively) and check each new parameter against it. If you already parsed it, return immediately.

answered Mar 08 '12 at 15:22

Blindy

65,249
10
91
131

1

+1. Also, order the array if you can (I'm not familiar with javascript and it's object representation, but I guess you can take the address of stuff), so you can use binary search, or maybe some other data structure that would fit the job better than an array. – Guido Mar 08 '12 at 15:28
My first thought was to say you can't get the numeric id for objects like that, but I'm actually decently sure you can; excellent suggestion! – Blindy Mar 08 '12 at 15:31
you can use a set, an object whose keys represent the elements of the set, and the values for those keys can be `null` (or some other dummy) – newacct Mar 09 '12 at 04:51

Matt · Answer 2 · 2012-03-08T15:25:50.690

You'll have to keep an array of array's visited within the flatten() function and check for their existence in there before you re curse into it. You'd have to pass the list of visited elements as a 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]
}

This will become expensive to check if your array is deep, so you could cheat and set an attribute on each array you visit, and check for it (but then of course, you're modifying the array (but not dramatically)).

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

Once weak maps are standardized/widely available, they would be a good alternative to adding a property to each array. See http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps#cycle-tolerant_graph_walking — Matthew Crumley, Mar 08 '12 at 18:47
Because arrays are also objects you could set a property to each array that you visit like array.visited = true; — IAMSAMMM, May 13 '18 at 06:11

score 2 · Answer 3 · answered Mar 08 '12 at 15:27

2

A convenient way to track already-visited arrays would be to add a "flat" property to each one, perhaps setting it to some unique value for each operation. No point messing with a separate map when each array is already a perfectly good object.

answered Mar 08 '12 at 15:27

Pointy

405,095
59
585
614

True if you own the object (ie you're free to change it as you wish), but that might not always be the case. Plus you'd have to either traverse it twice to reset the `flat` property back to false (and then you'd have to deal with recursion again), or you couldn't flatten an object twice. – Blindy Mar 08 '12 at 19:02
Yes - you could always go scrub off the marker afterwards I guess. – Pointy Mar 08 '12 at 19:37

score 1 · Answer 4 · answered Apr 24 '12 at 15:35

Another, more dirty way (but good for minimum fuss) is to just use the 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 did find this question looking for a better answer though, - although this might help someone wanting a nice hack ;-)

score 0 · Answer 5 · answered Mar 08 '12 at 16:02

In the real world, step 1 is to find the offending dev who handed you a self-referencing object and hit them with a stick.

The problem is solved, however, by eliminating them as self-references in place. Turn them into copies. Array.slice returns portions of arrays (including complete copies) without altering the original.

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

Note that this is only on the main array reference itself. Interior array references will still need to be changed since a copied reference still points at the same thing.

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

Detect infinite recursion?

5 Answers5

Linked