深入理解JavaScript中的尾调用与尾递归优化

尾调用与尾递归基础

什么是尾调用？

尾调用是函数式编程中一个核心概念，其定义简明扼要：若函数执行的最后一步是调用另一个函数，且该被调用函数的返回值直接作为当前函数的返回值返回，则此调用即为尾调用。示例如下：

function f(x) { 
 return g(x)
}

在函数f中，最后一步操作是调用函数g，且g的返回值被f直接返回，这构成了尾调用。

然而，以下两种情况并不属于尾调用：

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

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

上述代码中，第一种情况在调用函数g后还执行了其他操作，因此不属于尾调用，即便语义完全一致。第二种情况同样属于调用后还有操作，即使代码写在一行内。

尾调用之所以重要，是因为它不会在调用栈上创建新的堆栈帧，而是直接更新现有的调用栈，使得调用栈所占空间始终保持常量级别，从而节省内存并避免栈溢出风险。以上述示例为例，尾调用的调用栈结构如下：

[f(x)] => [g(x)]

当进入下一个函数调用时，前一个函数内部的局部变量（若存在）不再需要，因此调用栈长度不会增加，可以直接跳入被尾调用的函数。而在非尾调用的情况下，调用栈结构如下：

[f(x)] => [1 + g(x)]

可以看到，调用栈长度增加了一位，原因是函数f中的常量1必须保留在调用栈中，等待函数g调用返回后才能被计算回收。如果函数g内部还调用了函数h，则需等待h返回，依此类推，调用栈会越来越长。若此解释仍不够直观，尾调用还有一种更常见且直观的特殊形式——尾递归。

尾递归

顾名思义，若在一个尾调用中，函数最后的尾调用位置是该函数自身，则称为尾递归。递归应用广泛，但若实现不当，极易消耗大量内存导致栈溢出。通常解释递归会使用阶乘或斐波那契数列求和作为示例，此处以斐波那契数列为例。斐波那契数列是一个无限数列，从第三项开始，每项均为前两项之和：

0, 1, 1, 2, 3, 5, 8, 13, 21, ... 

若要计算第n项（从第0项开始）的值，使用递归是常见手段。若采用非尾递归形式，代码可写为：

function fibonacci(n) { 
 if (n === 0) return 0
 if (n === 1) return 1
 return fibonacci(n - 1) + fibonacci(n - 2)
}

以n=5为例，fibonacci函数的调用栈展开如下：

[fibonacci(5)]
[fibonacci(4) + fibonacci(3)]
[(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))]
[((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))]
[fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)]
[1 + 0 + 1 + 1 + 0 + 1 + 0 + 1]
5 

仅计算到第5项，调用栈长度已达8。稍复杂的递归若不加以注意，极易超出限制并消耗大量内存。若采用尾递归方式优化此过程，则可避免该问题，使用尾递归求斐波那契数列值的代码如下：

function fibonacciTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fibonacciTail(n - 1, b, a + b)
}

在此例中，每次调用后递归传入fibonacciTail函数的n值依次递减1，用于记录剩余递归次数。而a和b两个参数在每次递归计算后再次传入fibonacciTail函数，以调用栈形式表示如下：

fibonacciTail(5) === fibonacciTail(5, 0, 1) 
fibonacciTail(4, 1, 1) 
fibonacciTail(3, 1, 2) 
fibonacciTail(2, 2, 3) 
fibonacciTail(1, 3, 5) 
fibonacciTail(0, 5, 8) => return 5 

可见，每次递归并未增加调用栈长度，仅更新当前堆栈帧，从而避免了内存浪费和栈溢出风险。

注意

许多介绍尾调用和尾递归的文章至此结束，但实际情况并非如此简单。在未进行任何优化的情况下，尾调用与其他递归方式无异，仍会产生调用栈，同样存在栈溢出风险。尾递归之所以能优化，是因为每次递归调用时，当前作用域中的局部变量已无用，无需层层增加调用栈再在最后层层回收，当前调用帧可直接丢弃，这才是尾调用可优化的根本原因。

由于尾递归是尾调用的一种特殊形式，相对简单，在ES6未开启尾调用优化时，我们可以手动为尾递归进行优化。

尾递归优化方案

尾递归优化

改写为循环

优化的原因在于调用栈过多，只要避免函数内部的递归调用即可解决问题，其中一种方法是用循环替代递归。仍以斐波那契数列为例：

function fibonacciLoop(n, a = 0, b = 1) { 
 while (n--) {
 [a, b] = [b, a + b]
 }
 return a
}

这样，由于不存在函数的多次调用，将递归转变为循环，避免了调用栈的无限增加。

蹦床函数

另一种优化方法是借助蹦床函数，其原理是接受一个函数作为参数，在蹦床函数内部执行该函数；若函数返回值仍是函数，则继续执行。

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

可见，此处未在函数内部调用其他函数，而是在循环中重复调用同一函数，这也避免了增加调用栈长度。接下来需将原斐波那契函数改写为每次返回另一个函数的版本：

function 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(5)) // return 5 

实际的尾递归优化

实际上，真正的尾递归优化并非如上所示。上述两种方法均改写了尾递归函数本身，而真正的尾递归优化应是非入侵式的。以下是尾递归优化的一种实现：

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

随后将原fibonacciTail函数传入tailCallOptimize函数，得到一个新函数，该函数的执行过程即为经过尾递归优化的结果：

const fibonacciTail = tailCallOptimize(function(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fibonacciTail(n - 1, b, a + b)
})
fibonacciTail(5) // return 5 

下面解释这种优化方式的原理。

1. 首先通过闭包，在tailCallOptimize的作用域中保存唯一的active和accumulated。其中active指示尾递归优化过程是否开始，accumulated用于存放每次递归调用的参数。push方法将参数入列，shift方法将参数出列，保证先进先出的执行顺序。

2. 经过tailCallOptimize包装后返回的是一个新函数accumulator。执行fibonacciTail时实际执行的是该函数。第一次执行时，先将arguments[0]推入队列，active被标记为true，然后进入while循环，取出arguments[0]。在while循环执行中，会将参数类数组arguments[1]推入accumulated队列，然后直接返回undefined，不会递归调用增加调用栈。

3. 随后while循环会发现accumulated中又多了一个arguments[1]，再将arguments[2]推入队列。这样，在while循环中对accumulated的操作就是放进去一个、拿出来一个、再放进去一个、再拿出来一个，以此类推。

4. 最后一次while循环返回的即为尾递归的结果。

尾调用优化的引擎限制与识别

问题

实际上，当前的尾递归优化在引擎实现层面仍存在争议。以V8引擎为例，虽然已实现尾递归优化，但默认并未开启。V8团队更倾向于使用显式语法进行优化。原因在于他们认为尾调用优化仍存在一些问题，主要有两点：

难以辨别

在引擎层面消除尾递归是一种隐式行为，程序员在编写代码时可能并未意识到函数是否符合尾调用要求。此外，由于开启了尾调用优化，一旦出现死循环尾递归，也不会引发溢出，这使得问题难以辨别。以下介绍识别尾调用时需注意的几点：

首先，调用函数的方式并不重要，以下几种调用方式只要出现在尾调用位置上，均可被优化： + 普通调用：func(...) + 作为方法调用：obj.method(...) + 使用call或apply调用：func.call(..) 或 func.apply(...)

表达式中的尾调用

ES6的箭头函数可以使用一个表达式作为其函数体，函数返回值即为该表达式的返回值。在表达式中，以下几种情况可能包含尾调用：

三元运算符(? :)

const a = x => x ? f() : g() 

在此例中，函数f和g均位于尾调用位置。为便于理解，可将函数改写如下：

const a = x => { 
 if (x) {
 return f()
 } else {
 return g()
 }
}

可见，f和g的返回值均被直接返回，符合尾调用的定义。

逻辑运算符（|| 与 &&）

首先是||运算符：

const a = () => f() || g() 

此处函数f不在尾递归位置，而函数g在尾递归位置。为何如此？将函数改写后便清晰可见：

const a = () => { 
 const result = f()
 if (result) {
 return result
 } else {
 return g()
 }
}

||运算符的结果依赖于函数f的返回值，而非直接返回f的返回值，直接返回的仅有g函数的返回值。&&运算符的情况同理：

const a = () => f() && g() 

将函数改写为：

const a = () => { 
 const result = f()
 if (!result) {
 return result
 } else {
 return g()
 }
}

说明函数f也不在尾递归位置，而函数g在尾递归位置。

逗号运算符（,）

const a = () => (f(), g()) 

将函数改写一下：

const a = () => { 
 f()
 return g()
}

可见，在尾递归位置上的仍然只有一个g函数。

语句中的尾调用

在JS语句中，以下几种情况可能包含尾调用： + 代码块中（由{}分隔的语句） + if语句的then或else块中 + do-while，while，for循环的循环体中 + switch语句的执行代码块中 + try-catch语句的catch块中 + try-finally，try-catch-finally语句的finally块中

此外，return语句也可以包含尾调用。若return的表达式包含尾调用，则return语句包含尾调用，这无需多解释。

单独的函数调用不是尾调用

以下函数是否包含尾调用呢：

function foo() { 
 bar()
}

答案是否定的。先将函数改写如下：

function foo() { 
 bar()
 return undefined
}

可以看到，return语句返回的仅是undefined，而非bar函数的返回值，因此此处不存在尾调用。

尾调用只能出现在严格模式中

在非严格模式中，大多数引擎会在函数上增加以下两个属性： + func.arguments 包含调用函数时传入的参数 + func.caller 返回当前函数的调用者

但一旦进行尾调用优化，中间调用帧会被丢弃，这两个属性便失去了原本的意义。这也是在严格模式中不允许使用这两个属性的原因。

堆栈信息丢失

除了开发者难以辨别尾调用外，另一个原因是堆栈信息在优化过程中会丢失，这对调试极为不便。此外，一些依赖于堆栈错误信息进行用户信息收集分析的工具可能会失效。针对此问题，实现一个影子堆栈可解决堆栈信息缺失问题，但这种解决方式相当于对堆栈进行了模拟，不能保证始终符合实际虚拟机堆栈的真实状态。另外，影子堆栈的性能开销也非常大。

基于以上原因，V8团队建议使用特殊语法来指定尾递归优化。TC39标准委员会有一个尚无定论的提案，名为“从语法上指定尾部调行为”，该提案由来自Mozilla和微软的委员提出。提案的具体内容可查看相关链接，主要提出了三种手动指定尾调用优化的语法。

附手动优化语法

Return Continue

function factorial(n, acc = 1) { 
 if (n === 1) {
 return acc;
 }

 return continue factorial(n - 1, acc * n)
}

let factorial = (n, acc = 1) => continue 
 n == 1 ? acc
 : factorial(n - 1, acc * n);

// or, if continue is an expression form:
let factorial = (n, acc = 1) => 
 n == 1 ? acc
 : continue factorial(n - 1, acc * n);

Function sigil

// # sigil, though it's already 'claimed' by private state.
#function() { /* all calls in tail position are tail calls */ }

// Note that it's hard to decide how to readably sigil arrow functions.

// This is probably most readable.
() #=> expr
// This is probably most in line with the non-arrow sigil.
#() => expr

// rec sigil similar to async functions
rec function() { /* likewise */ } 
rec () => expr 

!-return

function () { !return expr }

// It's a little tricky to do arrow functions in this method.
// Obviously, we cannot push the ! into the expression, and even
// function level sigils are pretty ugly.

// Since ! already has a strong meaning, it's hard to read this as
// a tail recursive function, rather than an expression.
!() => expr

// We could do like we did for # above, but it also reads strangely:
() !=> expr

总结

以上就是本文的全部内容，希望本文的内容对大家的学习或工作能带来一定的帮助。如有任何疑问，欢迎留言交流。