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

今天药忘吃喽~ 2022-08-02 01:24 255阅读 0赞

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

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

*复制代码*

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

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

*复制代码*

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

*复制代码*

此时每次调用时，返回一个匿名函数，匿名函数执行相关的参数和局部变量将会释放，不会额外增加堆栈大小。  
优化调用：  
上例调用比较麻烦，优化如下：

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

*复制代码*

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

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

*复制代码*

虽然上例实现了我们想要的效果，但是trampoline函数还是有一定的局限性：  
  
  
1.假设你只传递一个参数给递归函数  
  
  
value = func(arg); 修改为 value = func.apply(func, arg);  
  
  
2.假设最后的返回值不是一个函数 关于更健壮性的实现，请看underscore-contrib中源码。  
  
  
转载声明：  
  
  
本文标题：Javascript中递归造成的堆栈溢出及解决方案

[Link 1]: http://www.html5cn.org/portal.php?mod=list&catid=17