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