Benjamin - 专注前端开发和用户体验

Javascript中递归造成的堆栈溢出及解决方案

点滴Javascript Benjamin 6926℃ 0评论

关于堆栈的溢出问题,在Javascript日常开发中很常见,Google了下,相关问题还是比较多的。本文旨在描述如何解决此类问题。
首先看一个实例(当然你可以使用更容易的方式实现,这里我们仅探讨递归):

function isEven (num) {
    if (num === 0) {
        return true;
    }

    if (num === 1) {
        return false;
    }

    return isEven(Math.abs(num) - 2);
}

//Outputs: true
console.log(isEven(10));

//Outputs: false
console.log(isEven(9));

当我们把参数改成10000时,运行下例会发生堆栈溢出:

function isEven (num) {
    if (num === 0) {
        return true;
    }

    if (num === 1) {
        return false;
    }

    return isEven(Math.abs(num) - 2);
}

//不同的javascript引擎报错可能不同
//Outputs: Uncaught RangeError: Maximum call stack size exceeded 
console.log(isEven(10000));

原因是每次执行代码时,都会分配一定尺寸的栈空间(Windows系统中为1M),每次方法调用时都会在栈里储存一定信息(如参数、局部变量、返回值等等),这些信息再少也会占用一定空间,成千上万个此类空间累积起来,自然就超过线程的栈空间了。那么如何解决此类问题?

使用闭包:

function isEven (num) {
    if (num === 0) {
        return true;
    }

    if (num === 1) {
        return false;
    }

    return function() {
        return isEven(Math.abs(num) - 2);
    }
}
//Outputs: true
console.log(isEven(4)()());

此时每次调用时,返回一个匿名函数,匿名函数执行相关的参数和局部变量将会释放,不会额外增加堆栈大小。

优化调用:

上例调用比较麻烦,优化如下:

function isEven (num) {
    if (num === 0) {
        return true;
    }

    if (num === 1) {
        return false;
    }

    return function() {
        return isEven(Math.abs(num) - 2);
    }
}

function trampoline (func, arg) {
    var value = func(arg);

    while(typeof value === "function") {
        value = value();
    }

    return value;
}
//Outputs: true
console.log(trampoline(isEven, 10000));

//Outputs: false
console.log(trampoline(isEven, 10001));

现在我们可以解决堆栈溢出问题了,但是不是感觉每次tarmpoline(isEven, 1000)这种调用方式不是很好,我们可以使用bind来绑定:

function isEven(n) {
    /**
     * [isEvenInner 递归]
     * @param  {[type]}  num [description]
     * @return {Boolean}     [description]
     */
    function isEvenInner (n) {
        if (n === 0) {
            return true;
        }

        if (n === 1) {
            return false;
        }

        return function() {
            return isEvenInner(Math.abs(n) - 2);
        }
    }
    /**
     * [trampoline 迭代]
     * @param  {[type]} func [description]
     * @param  {[type]} arg  [description]
     * @return {[type]}      [description]
     */
    function trampoline (func, arg) {
        var value = func(arg);

        while(typeof value === "function") {
            value = value();
        }

        return value;
    }

    return trampoline.bind(null, isEvenInner)(n);
}
//Outputs: true
console.log(isEven(10000));

//Outputs: false
console.log(isEven(10001));

虽然上例实现了我们想要的效果,但是trampoline函数还是有一定的局限性:
1.假设你只传递一个参数给递归函数
value = func(arg); 修改为 value = func.apply(func, arg);
2.假设最后的返回值不是一个函数

关于更健壮性的实现,请看underscore-contrib中源码。

感谢您的阅读,文中不妥之处还望批评指正,文章已同步至个人博客如果你有好的建议,欢迎留言,么么哒!

喜欢 (10)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽