Javascript 中的递归函数和深度跟踪
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9385560/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive functions in Javascript and depth-tracking
提问by CaptSaltyHyman
I'm writing a recursive function in JS and having some trouble. Let's start with this very basic function:
我正在用 JS 编写一个递归函数，但遇到了一些麻烦。让我们从这个非常基本的函数开始：
function traverse(thing)
{
if (typeof traverse.depth == 'undefined')
traverse.depth = 1;
else
traverse.depth ++;
if (thing.child)
traverse(thing.child);
}
So this works fine, and depthacts as a static var of sorts, but the problem is that in a language like C that has proper static vars, as you back out of the function, this variable would (ostensibly) decrease, so it is a true depth. If I have three boxes that contain three boxes and each of those contain three boxes, etc., we're essentially drilling down into the deepest one till there are no children, then backing out up a level to a sibling, and traversing its children. The problem with the above code is that the depth keeps increasing and increasing infinitely, even though the TRUTH depth may only be 3 or 4 from the oldest ancestor to the youngest child. If there are 80 siblings on each level, that depth counter is going to skyrocket.
所以这工作正常，并depth充当各种静态变量，但问题是在像 C 这样的语言中具有适当的静态变量，当你退出函数时，这个变量会（表面上）减少，所以它是一个真实深度。如果我有三个包含三个盒子的盒子，每个盒子都包含三个盒子，等等，我们基本上是深入到最深的一个直到没有孩子，然后返回一个级别到一个兄弟姐妹，并遍历它的孩子. 上面代码的问题是深度不断增加，无限增加，即使从最老的祖先到最年幼的孩子，真实深度可能只有3或4。如果每个级别有 80 个兄弟姐妹，那么深度计数器将会飙升。
How do I keep track of true depth in JS recursive functions?
如何跟踪 JS 递归函数的真实深度？
回答by Rob W
Don't attach the counter to the function. The counter is shared by all recursive calls, so the counter represents the number of function calls, instead of the recursion depth.
不要将计数器附加到函数上。计数器由所有递归调用共享，因此计数器表示函数调用的次数，而不是递归深度。
When depthis passed as a separate variable, the counter shows the true depth.
当depth作为单独的变量传递时，计数器显示真实深度。
function traverse(thing, depth)
{
if (typeof depth == 'number')
depth++;
else
depth = 1;
if (thing.child)
traverse(thing, depth);
}
回答by georg
Another (and perhaps nicer) solution would be to utilize JS functional programming strengths and use a high-order function to keep all depth-related housekeeping outside of the main function. Consider, for example, the following classic example:
另一个（也许更好）的解决方案是利用 JS 函数式编程的优势并使用高阶函数将所有与深度相关的内务处理保持在主函数之外。例如，考虑以下经典示例：
function fac(n) {
if(n < 3)
return n;
return n * fac(n - 1);
}
We want this one to break the recursion once its goes deeper than a given value. Let's code a wrapper:
我们希望这个函数在它比给定值更深时打破递归。让我们编写一个包装器：
function wrapDepth(fn, max) {
var depth = 0
return function() {
if (++depth > max)
throw "Too much recursion"
var out = fn.apply(null, [].slice.call(arguments, 0))
depth--;
return out;
}
}
Create a wrapper with max depth = 20:
创建一个最大深度 = 20 的包装器：
fac = wrapDepth(fac, 20)
and test:
并测试：
console.log(fac(10)) // 3628800
console.log(fac(100)) // Too much recursion
Note that we didn't make any change in the main function facitself, but still, its recursion depth is now under control.
请注意，我们没有对 main 函数fac本身进行任何更改，但它的递归深度现在仍处于控制之中。
回答by Mike Corcoran
why don't you just modify the function signature to take a thing and an index? So you would call it like:
你为什么不修改函数签名来获取一个东西和一个索引？所以你会这样称呼它：
function traverse(thing, idx)
...
if (condition)
traverse(thing.child, ++idx)
回答by Paul
Just add:
只需添加：
traverse.depth--;
Right before any return statements. So
就在任何 return 语句之前。所以
if(x === 5)
return thing;
Would become:
会成为：
if(x === 5){
traverse.depth--;
return thing;
}
And then add traverse.depth--;before your closing }of the function.
然后traverse.depth--;在关闭}函数之前添加。
回答by Selvakumar Arumugam
If I understood correctly, it looks to me like you want to track the depth of recursion.. but in your code you never decrement the depth as you finish 1 level in the recursion.
如果我理解正确，在我看来，您想跟踪递归的深度……但是在您的代码中，当您在递归中完成 1 个级别时，您永远不会减少深度。
I tried out a simple code and I think this what you wanted,
我尝试了一个简单的代码，我认为这是你想要的，
HTML:
HTML：
<div id="result"></div>
JS:
JS：
var result = document.getElementById('result');
var tmpArray = [1,2,3,4,5,6,7,8];
function depthTest() {
if (typeof depthTest.depth == 'undefined')
depthTest.depth = 0;
else
depthTest.depth++;
result.innerHTML += depthTest.depth;
if (typeof tmpArray[depthTest.depth] != 'undefined')
depthTest();
result.innerHTML += depthTest.depth;
depthTest.depth--;
}
depthTest(tmpArray);
OUTPUT:
输出：
012345678876543210
