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

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

function isEven (num) {    if (num === 0) {        return true;    }    if (num === 1) {        return false;    }    return isEven(Math.abs(num) - 2);}//Outputs: trueconsole.log(isEven(10));//Outputs: falseconsole.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: trueconsole.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: trueconsole.log(trampoline(isEven, 10000));//Outputs: falseconsole.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: trueconsole.log(isEven(10000));//Outputs: falseconsole.log(isEven(10001));

虽然上例实现了我们想要的效果，但是trampoline函数还是有一定的局限性：

1.假设你只传递一个参数给递归函数

value = func(arg); 修改为 value = func.apply(func, arg);

2.假设最后的返回值不是一个函数 关于更健壮性的实现，请看underscore-contrib中源码。

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

转载声明：

本文标题：Javascript中递归造成的堆栈溢出及解决方案

本文链接：http://www.zuojj.com/archives/1115.html，转载请注明转自Benjamin-专注前端开发和用户体验