ES6细节笔记（二）

ES6细节笔记（一）

0x04 尾调用优化

还记得递归函数吗？例如：求 1 + 2 + … + n的值，如果用递归算：

function sum(n) {
    if(n <= 0) {
         return 0
    }
    return n + sum(n-1)
}

持续的递归会产生一个栈的数据结构来保存每一次递归函数的状态，称为调用帧，直至这个函数返回成功，非常消耗内存。在递归次数过大的情况下，很容易发生『栈溢出』，如上面那个例子，输入参数n导致会产生n个调用帧，空间复杂度为O(n)，而ES6中的尾调用优化则是为了避免这种情况，可以使其空间复杂度变为O(1)，如何做到呢？

首先，上面那个函数并不能称为尾调用，尾调用就是在返回时只调用某个函数，类似下面这种情况：

// 伪代码
function a(...args1) {
    ...
    return a(...args2)
}

// 实例
function b(n) {
    if (n < 0) return 0
    return b(n - 1)
}

而下面这些实例都不能称为尾调用：

// case 1
function f(x) {
    let y = g(x)
    return y
}

// case 2
function f(x) {
    return g(x) + 1
}

// case 3
function f(x) {
    g(x)
}

若要使用尾调用优化需先将其修改称为尾调用优化的形式。

解释尾调用优化，我们先看下面几个例子，不难看出：

function f() {
    return g(3)
}
// 等价于
g(3)

// ------

function f(n) {
    let m = 2
    return g(m, n)
}
// 等价于
g(2, n)

// ------
function f(n) {
    if(n < 1) return 0
    return f(n-1)
}
f(3)
// 等价于
f(2)
// 等价于
f(1)
// 等价于
f(0)
// 等价于
0

可以看出，每执行到尾调用的时候，改函数之前的状态其实已经没有必要保存着了，所有必要信息都以参数的形式传递给了尾调用函数。因此：

在尾调用中，执行到尾调用，直接用尾调用函数替换掉当前正在执行的函数，而不使用栈来保存之前函数的状态，释放掉之前函数的内存，从而使其空间复杂度始终保持在O(1)，栈溢出永远不可能发生。

注意：由此看，下面这个函数同样不属于尾调用优化的范围：

function outer() {
    function inner() {
        return 1
    }
    return inner()
}

因为inner在outer的作用域范围中，是outer的状态之一。

在平时的编码使用函数递归的情况下，可以将迭代函数修改成尾函数来优化递归。例如上面的例子：

function sum(n) {
    if(n > 0) {
         return 0
    }
    return n + sum(n-1)
}

改成：

function sum(n, total = 0) {
    if(n <= 0) {
         return total
    }
    return sum(n-1, total + n)
}

可以得到同样的结果，同时触发了ES6的尾函数优化。

ES6细节笔记（目录）

Back