ES6中的尾递归优化

2019年05月26日Web前端

递归是我们经常会用到的,然而没有限制的递归,往往会引起爆栈的问题,于是尾递归的优势便体现了出来。

递归

假如我们需要实现1+2+3+4+....+n的一个小程序,用递归实现的话,如下:

function sum(x) {
    if (x === 1) {
        return 1;
    }
    return x + sum(--x);
}

递归正常值是没有问题的,

console.log( sum(10) );       // 55
console.log( sum(55555) );    // Uncaught RangeError: Maximum call stack size exceeded

当递归层数到达一定值后,就会出现爆栈了,当然不同浏览器的最大递归层数是不一样的。

尾递归

函数调用自身的过程,称为递归,如果最后调用的是自身,就称为尾递归。在ES6中,有了尾递归优化这个概念。我们将刚才的递归改写成尾递归:

function sum1(x, total) {
    if (x === 1) {
        return x + total;
    }
    return sum1(x - 1, x + total);
}

在普通递归时,最后return了x + sum(--x),即每次调用下一个sum函数时,都需要保存当前作用域下的其他变量(比如x),所以很容易出现栈溢出的问题。

而尾递归中,由于最后返回的是函数,往往不需要保留先前的东西,仅仅记录下一次调用的函数即可,所以可以节省大量的内存。 在chrome下尝试:

console.log( sum1(10, 0) ); // 55
console.log( sum1(55555, 0) ); // Uncaught RangeError: Maximum call stack size exceeded

依旧是爆栈了。 查阅了资料发现,v8中尾递归优化是默认关闭的,尝试了以下方法均以失败告终:

  1. 严格模式下运行(chrome74.0.3729.157 64位版本)。
  2. chrome下开启Experimental JavaScript(版本同上)。
  3. node环境下(v8.11.1)。
  4. mac safari浏览器(12.0.3版本)。

至于为何没有默认开启呢?可以查看下这篇文章:尾递归的后续探究

其他方式

如果想实现递归但又怕爆栈这种情况呢?我们可以使用while循环。

function sum2(n) {
    var sum = 0;
    while (n > 0) {
        sum += n;
        n--;
    }
    return sum;
}

console.log( sum2(10) ); // 55
console.log( sum2(55555, 0) ); // 1543206790

以循环的方式也是可以完成的。

整个demo地址:github