检测无限递归？

Question

让我们假设我有一个爬过数组的函数...

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将爬过代码,并且遇到的每个数组将以递归方式进入该数组并返回值,以便您拥有一个平面数组.

这有效,直到我们有一个数组,如:

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

这显然会产生无限递归:

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

如何在不修改数组的情况下检测此行为,以便该函数可以处理此问题？

Answer 1

如果检测递归是必需的,那么你将不得不为它交换内存空间:创建一个你解析的对象数组(递归发送的参数)并检查每个新参数.如果您已经解析过它,请立即返回.

Answer 2

您必须在函数中保留一个已访问数组的数组flatten()，并在重新诅咒它之前检查它们是否存在。您必须将访问过的元素列表作为第二个参数传递给recurse尽管。

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

检查数组是否很深将变得昂贵，因此您可以作弊并在访问的每个数组上设置一个属性，然后检查它（但当然，您正在修改数组（但不是很大））。

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