ES6中的尾递归优化

2019年05月26日Web前端0

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

递归

假如我们需要实现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。

ES6

目录