1、尾调用函数

尾调——Tail Call，即一个出现在另一个函数“结尾”处的函数调用，如

  1. function foo(x) {
  2.   return x;
  3. }
  5. function bar(y) {
  6.   const x = y + 1;
  7.   return foo(x); // Tail call
  8. }

函数调用时，会形成调用栈，调用某个函数时会将其压入栈，当它 return 后就会出栈。上面例子开始调用 foo 函数的时候， foo 函数的栈帧并不是必须的，完全可以复用 bar 函数的栈帧。
故尾调优化（Tail Call Optimization，TCO） 即：当侦测到当前函数是尾调用时，就复用之前的栈帧。通过 TCO 优化，我们就节省了一个栈帧的空间。如果尾调的数量有成千上万个的话，TCO 就可以很好的避免 Stack Overflow 了

2、尾递归函数

首先，来看一个递归函数，这个 sum 函数是用来求 1 ~ n 的正整数和的，如sum(2)=3, sum(3)=6。很明显它不是一个尾调函数

  1. function sum(n) {
  2.   if (n <= 1) return n;
  3.   return n + sum(n - 1);
  4. }

若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归，如

  1. function sum(n, pre = 0) {
  2.   if (n <= 1) return n + pre;
  3.   return sum(n - 1, n + prev);
  4. }

其他例子

  1. // 一般的实现方式
  2. function fibonacci(n) {
  3.     if(n==0 || n == 1)
  4.         return n;
  5.     return fibonacci(n-1) + fibonacci(n-2);
  6. }
  8. // 尾调用优化后
  9. 'use strict'
  10. function fibonacci_opt(n, current = 0, next = 1) {
  11.     if(n <= 1) {
  12.         return next
  13.     }
  14.     return fibonacci_opt(n - 1, next, next+current)
  15. }
  17. fibonacci_opt(5)

3、说明

ES6中的尾调用优化的条件：

  • 严格模式下。
  • 尾调用不访问当前栈帧的变量（也就是说函数不是一个闭包）
  • 在函数内部，尾调用是最后一条语句。
  • 尾调用的结果作为函数值返回。

虽然尾调用优化是 ES6 规范中的一部分，但其实大部分 JS 引擎都没有实现。

参考资料