Javascript和深度跟踪中的递归函数

Question

我正在JS编写递归函数并遇到一些麻烦.让我们从这个非常基本的功能开始:

function traverse(thing)
{
    if (typeof traverse.depth == 'undefined')
        traverse.depth = 1;
    else
        traverse.depth ++;

    if (thing.child)
        traverse(thing.child);
}

所以这样可以正常工作,并且depth可以作为静态var的各种类型,但问题是在像C这样具有适当静态变量的语言中,当你退出函数时,这个变量会(表面上)减少,所以它是一个真实的深度.如果我有三个盒子,其中包含三个盒子,每个盒子包含三个盒子等等,我们基本上钻到最深的盒子里,直到没有孩子,然后退出一个级别给一个兄弟姐妹,并穿过它的孩子.上述代码的问题在于深度不断增加和增加,即使从最古老的祖先到最小的孩子,TRUTH深度可能只有3或4.如果每个级别上有80个兄弟姐妹,那个深度计数器将会飙升.

如何跟踪JS递归函数的真实深度？

Answer 1

请勿将计数器连接到该功能.计数器由所有递归调用共享,因此计数器表示函数调用的数量,而不是递归深度.

当depth作为单独的变量传递时,计数器显示真实的深度.

function traverse(thing, depth)
{
    if (typeof depth == 'number')
        depth++;
    else
        depth = 1;

    if (thing.child)
        traverse(thing, depth);
}

Answer 2

另一个(也许更好的)解决方案是利用JS函数编程优势并使用高阶函数将所有与深度相关的内务处理保留在主函数之外.例如,考虑以下经典示例:

function fac(n) {
    if(n < 3)
        return n;
    return n * fac(n - 1);
}

我们希望这个在递归超过给定值时打破递归.让我们编写一个包装器:

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

创建一个最大深度为20的包装器:

fac = wrapDepth(fac, 20)

并测试:

 console.log(fac(10)) // 3628800
 console.log(fac(100)) // Too much recursion

请注意,我们没有对main函数fac本身进行任何更改,但仍然可以控制其递归深度.