很多浏览器引擎并没有支持尾递归调用优化，即便支持，也要求代码运行环境在 strict mode 下
举个fibonacci 数列求和的例子
const fibonacci = n => {
if (n === 0) return 0
if (n === 1) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}
fibonacci 数列求和非常耗费内存，如果用尾递归进行优化：
const fibonacciTail = (n, a = 0, b = 1) => {
if (n === 0) return a
return fibonacciTail(n - 1, b, a + b)
}
每次调用 fibonacciTail 函数后，会继续递归调用 fibonacciTail，函数的 n 会依次递减 1，它实际上是用来记录递归剩余求和的次数。而 a 和 b 两个参数在每次递归时也会在计算后再次传入 fibonacciTail 函数，最终返回值为 a，a 是上一次 a + b 的结果。这样每次递归都不会增加调用栈的长度，只是更新当前的堆栈帧而已。也就避免了内存的浪费和爆栈的危险。
对于不支持尾递归调用优化的场景，一般有两个优化方案：
- 1、将递归改为循环
const fibonacciLoop = (n, a = 0, b = 1) => {
while (n--) {
[a, b] = [b, a + b]
}
return a
}
- 2、蹦床函数
蹦床函数并没有实现真正的尾递归，它只是将整个执行过程拆散，还是类似循环的效果：每次产生一个结果，该结果将会对下一次执行产生影响，就像蹦床一样，越蹦越高。我们看蹦床函数接受一个函数作为参数，在蹦床函数内部执行这个函数，如果执行结果，也就是该函数的返回值还是一个函数，那么就继续执行。一直到返回值不再是一个函数时，我们返回最终的结果。
const trampoline = func => {
while (func && func instanceof Function) {
func = func()
}
return func
}
const fibonacciFunc = (n, a = 0, b = 1) => {
if (n > 0) {
[a, b] = [b, a + b]
return fibonacciFunc.bind(null, n - 1, a, b)
} else {
return a
}
}
使用时：
trampoline(fibonacciFunc(9)) //34
这算是"奇淫技巧"，并不是实现了真正的尾递归调用优化。
真正实现尾递归调用优化的方案：
const tailCallopt = func => {
let result
let started = false
const accumulated = []
return function asscumlator() {
accumulated.push(arguments)
if (!started) {
started = true
}
while (accumulated.length) {
result = func.apply(this, accumulated.shift())
}
started = false
return result
}
}
const fibonacciTailOpt = tailCallopt(function(n, a = 0, b = 1) {
if (n === 0) return a
return fibonacciTailOpt(n - 1, b, a + b)
})
fibonacciTailOpt(9) //34
tailCallOpt 接受一个待优化的函数 func，返回一个新的 accumulator 函数。执行 fibonacciTailOpt(9) 就是第一步执行 accumulator。
第一次执行 accumulator 时，先将参数推入 accumulated 数组当中，started 标记为 true。然后进入 while 循环，循环中执行待优化的 func 函数，func 这个函数执行过程中需要保证调用 tailCallOpt 函数的返回值，这里为 fibonacciTailOpt；第二次执行 accumulator，将新的参数加入 accumulated 数组；这样 accumulated 数组长度始终不为零，循环继续进行。
整个过程就是 accumulated 数组放进去一个参数，执行一次，得到结果，accumulated 清空；再放进去新的参数，执行得到结果，accumulated 再清空，以此类推。直到 func 返回了基本类型值（非函数值），这时候 accumulated 数组不会再有新的参数进来，因此返回最终结果。
end
你品，你细品
网友评论