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

发表于 | 分类于 |

博客园

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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时，运行下例会发生堆栈溢出：//Outputs: Uncaught RangeError: Maximum call stack size exceeded

使用闭包：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)()());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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));