/ ECMAScript6

ECMAScript6 之尾调用优化

标签: ECMAScript 6 javaScript

定义

尾调用(Tail Call)是函数式编程的一个重要概念,本身非常简单,一句话就能说清楚,就是指某个函数的最后一步是调用另一个函数。

简单的理解就是在函数体内,最后一行 return 了一个函数调用。注:仅仅只能是函数调用,任何其他的形式都不能认为是尾调用。

以下都不属于尾调用

// 情况一
function f(x){
    let y = g(x)
    return y
}

// 情况二
function f(x){
    return g(x) + 1
}

// 情况三
function f(x){
    g(x)
}

以下属于尾调用,函数最后 return 了一个和 f 函数无关的 g 函数。

function f(){
    return g(x)
}

理解

函数的调用会参数很多的信息,这些信息都会被保存在一个调用帧中(包括参数,变量等信息),如果在函数 A 中调用了 B ,那么在函数 A 的调用帧中,会产生一个 B 的调用帧,当 B 执行结束后,将函数 B 的调用结果返回到 A 的调用帧中,这样就形成了一个函数的调用栈。

试想一下,上述情况中,假如 A 的调用帧在执行 B 的时候已经和 B 无关了(所有有关的信息通过参数传入,B 函数的调用帧保存了参数信息),并且 B 的调用是 A 中需要执行的最后一行代码,也就是说 A 的调用帧中的信息在 B 执行的时候,并且在 B 执行结束之后都是没用的,所以针对于这种情况,我们可以直接舍弃 A 的调用帧,直接把 B 的调用帧给提到 A 的调用帧的位置,这样调用栈就少了一层。

代码解释

function f() {
    let m = 1
    let n = 2
    return g(m + n)
}
f()

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

// 等同于
g(3)

这就叫做“尾调用优化”( Tail call optimization ),即只保留内层函数的调用帧。如果所有函数都是尾调用,那么完全可以做到每次执行时,调用帧只有一项,这将大大节省内存。这就是“尾调用优化”的意义。

尾递归

函数调用自身,称为递归。如果尾调用自身,就称为尾递归。

在写递归时,经常会出现内存溢出的情况,由于函数调用自身,导致调用栈不断增加,当内存不足时,容易发生栈溢出的错误。

但是结合上面提出的尾调用优化,试想一下,如果函数的递归符合尾调用优化,那么是不是不会存在栈溢出的情况了,因为函数调用栈始终只有一层。

ok 一个简单的递归例子,阶乘函数

function factorial(n) {
    if (n === 1) return 1
    return n * factorial(n - 1)
}

factorial(5) // 120

很明显,这个函数并没有实现尾调用优化,函数执行的最后一行包含了对当前调用帧中信息的引用,即 n

我们改写一下,让它符合尾调用优化

// 将阶乘的结果当做函数参数传入
function factorial(n, total) {
    if (n === 1) return total
    return factorial(n - 1, n * total)
}

factorial(5, 1) // 120

另外一个例子, Fibonacci 数列

未经优化

function Fibonacci (n) {
    if ( n <= 1 ) {return 1}
    return Fibonacci(n - 1) + Fibonacci(n - 2)
}

Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出

已优化

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
    if( n <= 1 ) {return ac2}
    return Fibonacci2 (n - 1, ac2, ac1 + ac2)
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

可见尾调用的优化的关键点在于将包裹函数中数据的引用作为返回函数的参数。

当前环境下的实现

实际测试下来,目前的环境基本都没有实现尾调用优化,虽然在阮老师提到严格模式是实现的,但经过测试并没有,所有要实现尾调用优化,还要等等。

但,正式的没有,兼容的还是有的。

一个简单递归函数

function sum(x, y) {
    if (y > 0) {
        return sum(x + 1, y - 1);
    } else {
        return x;
    }
}

sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)

很明显调用栈溢出。

实现一个蹦床函数来讲递归转换为循环执行。

function trampoline(f) {
    while (f && f instanceof Function) {
        f = f()
    }
    return f
}

但这很明显有个缺点,就是我们得修改我们原本的递归函数,因为这个蹦床函数调用传入的函数的返回值是一个函数,而不是函数调用,所以我们需要修改我们的递归函数。

function sum(x, y) {
    if (y > 0) {
        return sum.bind(null, x + 1, y - 1)
    } else {
        return x
    }
}

trampoline(sum(1, 100000))
// 100001

这个无疑会增加编写代码的难度。那么有一个完美的解决方案吗?有

function tco(f) {
    var value
    var active = false
    var accumulated = []
    
    return function accumulator() {
        accumulated.push(arguments)
        if (!active) {
            active = true
            while (accumulated.length) {
                value = f.apply(this, accumulated.shift())
            }
            active = false
            return value
        }
    }
}

var sum = tco(function(x, y) {
    if (y > 0) {
        return sum(x + 1, y - 1)
    }
    else {
        return x
    }
})

sum(1, 100000)
// 100001

具体的执行过程其实就是一个保存参数的过程,关键点在于 active

至于详细的解释就看 《ECMAScript 6 入门》 吧。

注: 上面的例子大多数来自《ECMAScript 6入门》这本书。