javascript中函数递归堆栈溢出问题思考

发表于 | 分类于

这几天在用node.js写一个递归遍历文件树的功能，一直都有一个概念，就是递归次数过多，程序可能崩溃。但是一直没有仔细想过这个问题的原因,这里又多思考了一下，参考一下维基百科，每次函数递归调用的时候，在调用栈的顶部都要增加一条记录，记录子函数的返回地址，这样，随着递归深度的加深,用栈中一次讲调用函数返回地址入栈，当入栈次数过多，超过栈顶时，便会报栈溢出错误。

后面自己写了两个测试小程序，去测试了一下。

代码1: 递归判断数字是否是偶数，是返回1，否返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
function is_even_number(number){
    // 这里默认传入的是大于1正整数，未做数字有效性判断
    if(0 === number){
        return 1;
    } else if( 1 === number) {
        return 0;
    } else {
        console.log('number::',number);
        return is_even_number(number - 2)
    }
}
is_even_number(30000);

测试发现，当number足够大的时候，程序运行一段时候就会报堆栈溢出的错误。 由于node.js屏蔽了堆栈分配等细节，大概可以猜测，因为随着递归深度加深，return前不断执行子函数，不断有局部变量和子函数返回地址等入栈，所记录的上下文环境越来越大，超过栈顶后便报错了。参考网上的例子，要解决这样的问题，关键就是函数返回的时候，直接返回一个结果，而不是执行一个子函数后返回，这样就避免了在调用栈栈顶对子函数的返回地址进行记录，通过这个方法，避免堆栈溢出。

代码2: 递归判断数字是否是偶数，是返回1，否返回0 ， 使用闭包，递归调用放在匿名函数中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function is_even_number(number){
    // 这里默认传入的是大于1正整数，未做数字有效性判断
    if(0 === number){
        return 1;
    } else if( 1 === number) {
        return 0;
    } else {
        console.log('number::',number);
        return function() {
            return is_even_number(number - 2)
        }
    }
}
// 将递归执行的函数包裹在包装函数中
functon wrapper_func(func, number) {
    let  ret = func(number);
    while('function' === typeof ret) {
        ret = ret()
    }
    return ret;
}
wrapper_func(is_even_number,1000000);

测试发现,此时运行不在出现堆栈溢出的错我，但是由于闭包记录了一些上下文，不断执行ret()的时候，闭包链也越来越长，无限次运行时，可能会出现内存泄漏。