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的尾函数优化。