检测无限递归？

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

我该如何在不修改数组的情况下检测到这种行为，以便函数能够处理它？

- Incognito

---

我们能否维护我们已经爬取的内容，如果我们已经爬取了该数组，则处于上述描述的情况... - Nitin Midha

请查看这篇文章。它基本上展示了如何编写一个函数装饰器来限制递归深度。 - georg

Answer 1

如果检测递归是必要的，那么您需要用内存空间来代替：创建一个对象数组（已解析的参数），并针对每个新参数进行检查。如果已经解析，则立即返回。

- Blindy

---

+1。如果可能的话，对数组进行排序（我不熟悉JavaScript和它的对象表示，但我猜你可以获取stuff的地址），这样你就可以使用二分查找，或者其他更适合此任务的数据结构，而不是数组。 - Guido

我的第一个想法是说你不能像那样获取对象的数字ID，但我相当确定你可以；这是个很好的建议！ - Blindy

你可以使用一个集合，这个对象的键表示集合中的元素，而这些键的值可以是null（或其他一些虚拟值）。 - newacct

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

- Matt

---

一旦弱映射被标准化/广泛使用，它们将是向每个数组添加属性的良好替代方案。请参见http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps#cycle-tolerant_graph_walking - Matthew Crumley

因为数组也是对象，所以您可以为每个访问的数组设置一个属性，例如array.visited = true; - IAMSAMMM

Answer 3

一种方便跟踪已访问数组的方法是为每个数组添加一个“flat”属性，可以为每个操作设置为某些唯一值。当每个数组已经是一个完美的对象时，没有必要使用单独的映射。

- Pointy

---

如果您拥有该对象（即您可以自由更改它），则返回True，但这并不总是情况。此外，您必须要遍历两次才能将“flat”属性重置为false（然后您必须再次处理递归），或者您不能对一个对象进行两次展平。 - Blindy

是的 - 我想你之后可以擦掉标记笔。 - Pointy

Answer 4

另一种更加简单粗暴的方法（但适用于最小的麻烦）是直接使用JSON编码器：

var is_recursive = false;

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

虽然我发现这个问题想要一个更好的答案，但这可能会帮助一些想要不错的技巧的人 😉

- odinho - Velmont

Answer 5

在现实世界中，第一步是找到那个给你一个自我引用对象的罪魁祸首，并用棍子打他们。

然而，问题可以通过在原地消除它们作为自我引用来解决。将它们转化为副本。Array.slice返回数组的部分（包括完整的副本），而不改变原始数组。

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

请注意，这仅适用于主数组引用本身。由于复制的引用仍然指向相同的内容，因此仍需要更改内部数组引用。

另外，如果您可以做出关于绝对不会出现的字符的假设，您可能会发现切片/连接非常有帮助。

- Erik Reppen