如何防止无限递归

Question

我正在尝试递归打印 jQuery 的内容。我计划使用它来根据已知“jQuery 签名”的小型数据库来分析 jQuery 的现有实例（在页面中加载），以确定已进行哪些更改（即已加载哪些插件、修改了哪些功能等） .)。

为此，我有一个小函数：

function recurse(obj, iter){
    var padding = (new Array(iter + 1)).join("  ") + ">";

    for (var i in obj){
    document.writeln(padding + i + "<br/>");

    if (iter < 5)
        recurse(obj[i], iter + 1);
    }
}

当我执行这个时：

recurse(jQuery, 1);

我得到这样的结果：

  >prototype
    >init
      >prototype
        >init
          >prototype
        >selector
        >jquery
          >0

.... On and on and on .....

我的问题是，在一开始，你可以看到 prototype 然后 init 一遍又一遍地重复。它停止在 5 深度的唯一原因是 if (iter < 5) 检查。如果没有限制，它就会永远重复[原文如此？]。迭代限制有帮助，但如果关键函数有 6 层深度怎么办？本质上，我不知道应该对这个迭代进行什么限制，或者是否应该有一个。

相反，我认为必须有某种算法可以防止永无止境的递归。这样的算法存在吗？或者我应该改变遍历 jQuery 的方式？谢谢，

Answer 1

您可以跟踪已经看到的值，并在再次看到该值时退出。

function recurse(obj) {
  var marker = '__' + new Date().getTime() + '__';
  function r(obj, iter) {
    if (marker in obj) return;

    var padding = (new Array(iter + 1)).join("  ") + ">";
    obj[marker] = true;

    for (var i in obj) {
      if (!obj.hasOwnProperty(i) || i === marker) continue;

      document.writeln(padding + i + "<br/>");

      recurse(obj[i], iter + 1);
    }
  }
  r(obj, 0);      
}

现在这当然有一个缺点，那就是让你遍历的对象图充满额外的属性，但对于某些应用程序来说这不是问题。另外，用时钟来做一个“独特”的标记确实很蹩脚；您可能只想使用一个计数器，或者只是一个固定的无意义字符串。

编辑 - 另外，另一个问题（也存在于原始代码中）是，这确实应该检查“obj”值是否真的是对象。如果它们是标量，那么真的没有必要做任何事情。您只需要在检查标记后立即进行“typeof”检查，如果您看到 null、数字、字符串或布尔值，则只需返回即可。

Answer 2

您的递归缺少基本情况。请参阅递归的定义。您引入了（深度 < 5） 的任意基本情况。也许改为使用数组的长度，或者正如 Pointy 指出的那样，使用 hasOwnProperty 检查来跳过递归调用。

Answer 3

除非我遗漏了一些东西，否则您需要做的就是跳过字符串（如果您使用允许字符串索引的现代浏览器，否则没关系）和 init 函数，它是 jQuery 自引用，为您提供无限递归

function recurse(obj, iter){
    var padding = (new Array(iter + 1)).join("  ") + ">";

    for (var i in obj){
        document.writeln(padding + i + "<br/>");
        if (i != 'init' && typeof obj[i] != 'string') 
            recurse(obj[i], iter + 1);
    }
}

Answer 4

正如几个答案所说：您的算法必须包含适当的中断情况以防止无限递归。

但是，如果您无法控制算法的输入，会发生什么情况？

对于这种情况，或者只是出于开发目的，您可以使用以下内容：

function acmeRecursion(){
  var count = localStorage.getItem("count");
  if(count>50){
    throw new Error("recursion limit exceeded");
  }
  count++;

  //put your logic here
}

Answer 5

根据 Pointy 的答案（理想情况下这将是一条注释，但是可惜，代码在这些中效果不佳），更好的解决方案可能是将一个对象传递给递归函数，该函数将跟踪您的对象我们已经看过了。像这样的东西：

var recurse = function(obj)
{
    var seen = {};
    var inner = function(obj, padding)
    {
        for (var i in obj)
        {
            if (!(obj[i] in seen))
            {
                document.writeln(padding + i + '<br />');
                seen[obj[i]] = true;
                inner(obj[i], padding + '  ');
            }
        }
    };
    return inner(obj, '');
};

为了简单起见，它使用闭包而不是参数来传递 seen 对象，但基本概念是相同的。

这种方法的优点是不会向正在遍历的对象添加额外的属性。

编辑：我本想解释这一点，但忘了。我没有使用 hasOwnProperty这里是因为在打印对象图的情况下，您可能确实希望看到继承的属性。