Javascript中递归造成的堆栈溢出及解决方案
关于堆栈的溢出问题,在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中源码。
感谢您的阅读,文中不妥之处还望批评指正,文章已同步至个人博客如果你有好的建议,欢迎留言,么么哒!
转载声明:
本文标题:Javascript中递归造成的堆栈溢出及解决方案
本文链接:http://www.zuojj.com/archives/1115.html,转载请注明转自Benjamin-专注前端开发和用户体验
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。