编程小贴士

给你的编程提供小点子


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

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

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return isEven(Math.abs(num) – 2);
  9. }
  10. //Outputs: true
  11. console.log(isEven(10));
  12. //Outputs: false
  13. console.log(isEven(9));

 

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

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return isEven(Math.abs(num) – 2);
  9. }
  10. //不同的javascript引擎报错可能不同
  11. //Outputs: Uncaught RangeError: Maximum call stack size exceeded
  12. console.log(isEven(10000));

 

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

使用闭包:

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return function() {
  9.         return isEven(Math.abs(num) – 2);
  10.     }
  11. }
  12. //Outputs: true
  13. console.log(isEven(4)()());

 

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

优化调用:

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

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return function() {
  9.         return isEven(Math.abs(num) – 2);
  10.     }
  11. }
  12. function trampoline (func, arg) {
  13.     var value = func(arg);
  14.     while(typeof value === “function”) {
  15.         value = value();
  16.     }
  17.     return value;
  18. }
  19. //Outputs: true
  20. console.log(trampoline(isEven, 10000));
  21. //Outputs: false
  22. console.log(trampoline(isEven, 10001));

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

  1. function isEven(n) {
  2.     /**
  3.      * [isEvenInner 递归]
  4.      * @param  {[type]}  num [description]
  5.      * @return {Boolean}     [description]
  6.      */
  7.     function isEvenInner (n) {
  8.         if (n === 0) {
  9.             return true;
  10.         }
  11.         if (n === 1) {
  12.             return false;
  13.         }
  14.         return function() {
  15.             return isEvenInner(Math.abs(n) – 2);
  16.         }
  17.     }
  18.     /**
  19.      * [trampoline 迭代]
  20.      * @param  {[type]} func [description]
  21.      * @param  {[type]} arg  [description]
  22.      * @return {[type]}      [description]
  23.      */
  24.     function trampoline (func, arg) {
  25.         var value = func(arg);
  26.         while(typeof value === “function”) {
  27.             value = value();
  28.         }
  29.         return value;
  30.     }
  31.     return trampoline.bind(null, isEvenInner)(n);
  32. }
  33. //Outputs: true
  34. console.log(isEven(10000));
  35. //Outputs: false
  36. console.log(isEven(10001));


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


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


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


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

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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>