尾调用和尾递归

尾调用

尾调用是函数式编程中一个很重要的概念，当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用。函数调用可以是下面方式中的任意一种：

• 函数调用：func(···)
• 方法调用：obj.method(···)
• call调用：func.call(···)
• apply调用：func.apply(···)

并且只有下列表达式会包含尾调用：

• 条件操作符：? :
• 逻辑或：||
• 逻辑与：&&
• 逗号：, 来看下面的例子：

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

  f() 和 g() 都在尾部。

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

  g() 有可能是尾调用，f() 不是，因为上述写法和下面的写法等效：

  const a = () => {
      const fResult = f(); // not a tail call
      if (fResult) {
          return fResult;
      } else {
          return g(); // tail call
      }
  };

  只有当 f() 的结果为false的时候，g() 才是尾调用。

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

  g() 有可能是尾调用，f() 不是，因为上述写法和下面的写法等效：

  const a = () => {
      const fResult = f(); // not a tail call
      if (fResult) {
          return g(); // tail call
      } else {
          return fResult;
      }
  };

  只有当 f() 的结果为true的时候，g() 才是尾调用。

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

  g() 是尾调用，因为上述写法和下面的写法等效：

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

  函数在调用的时候会在调用栈（call stack）中存有记录，每一条记录叫做一个调用帧（call frame），每调用一个函数，就向栈中push一条记录，函数执行结束后依次向外弹出，直到清空调用栈，参考下图：

  function foo () { console.log(111); }
  function bar () { foo(); }
  function baz () { bar(); }
  baz();

  
  造成这种结果是因为每个函数在调用另一个函数的时候，并没有 return 该调用，所以JS引擎会认为你还没有执行完，会保留你的调用帧。

baz() 里面调用了 bar() 函数，并没有 return 该调用，所以在调用栈中保持自己的调用帧，同时 bar() 函数的调用帧在调用栈中生成，同理，bar() 函数又调用了 foo() 函数，最后执行到 foo() 函数的时候，没有再调用其他函数，这里没有显示声明 return，所以这里默认 return undefined。

foo() 执行完了，销毁调用栈中自己的记录，依次销毁 bar() 和 baz() 的调用帧，最后完成整个流程。

如果对上面的例子做如下修改：

function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }
baz();

这里要注意：尾调用优化只在严格模式下有效。

在非严格模式下，大多数引擎会包含下面两个属性，以便开发者检查调用栈：

• func.arguments: 表示对 func最近一次调用所包含的参数。
• func.caller: 引用对 func最近一次调用的那个函数。

在尾调用优化中，这些属性不再有用，因为相关的信息可能以及被移除了。因此，严格模式(strict mode)禁止这些属性，并且尾调用优化只在严格模式下有效。

如果尾调用优化生效，流程图就会变成这样：

我们可以很清楚的看到，尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，只要直接用内层函数的调用记录取代外层函数的调用记录就可以了，调用栈中始终只保持了一条调用帧。

这就叫做尾调用优化，如果所有的函数都是尾调用的话，那么在调用栈中的调用帧始终只有一条，这样会节省很大一部分的内存，这也是尾调用优化的意义。

尾递归

讲尾递归之前先来看看什么是递归，当一个函数调用自身，就叫做递归，就像下面这样：

function foo () {
    foo();
}

上面这个操作就叫做递归，但是注意了，这里没有结束条件，是死递归，所以会报栈溢出错误的，写代码时千万注意给递归添加结束条件。

那么什么是尾递归？前面我们知道了尾调用的概念，当一个函数尾调用自身，就叫做尾递归，就像下面这样：

function foo () {
    return foo();
}

那么尾递归相比递归而言，有哪些不同呢？ 我们通过下面这个求阶乘的例子来看一下：

function factorial (num) {
    if (num === 1) return 1;
    return num * factorial(num - 1);
}
factorial(5);            // 120
factorial(10);           // 3628800
factorial(500000);       // Uncaught RangeError: Maximum call stack size exceeded

上面是使用递归来计算阶乘的例子，操作系统为JS引擎调用栈分配的内存是有大小限制的，如果计算的数字足够大，超出了内存最大范围，就会出现栈溢出错误。这里500000并不是临界值，只是我用了一个足够造成栈溢出的数。

如果用尾递归来计算阶乘呢？

'use strict';

function factorial (num, total) {
    if (num === 1) return total;
    return factorial(num - 1, num * total);
}
factorial(5, 1);                // 120
factorial(10, 1);               // 3628800
factorial(500000, 1);           // 分情况

注意，虽然说这里启用了严格模式，但是经测试，在 Chrome 和 Firefox 下，还是会报栈溢出错误，并没有进行尾调用优化，Safari 浏览器进行了尾调用优化，factorial(500000, 1) 结果为 Infinity ，因为结果超出了JS可表示的数字范围，如果在node v6版本下执行，需要加 –harmony_tailcalls 参数（node–harmony_tailcalls test.js），但是node最新版本已经移除了 –harmony_tailcalls 功能。

通过尾递归，我们把复杂度从 O(n) 降低到了 O(1) ，如果数据足够大的话，会节省很多的计算时间。由此可见，尾调用优化对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。

尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。
要做到这一点，需要把函数内部所有用到的中间变量改写为函数的参数，就像上面的 factorial() 函数改写一样。这样做的缺点就是语义不明显，要计算阶乘的函数，为什么还要另外传入一个参数叫total？
解决这个问题的办法有两个：

• ES6参数默认值

  'use strict';
  function factorial (num, total = 1) {
      if (num === 1) return total;
      return factorial(num - 1, num * total);
  }
  factorial(5);                // 120
  factorial(10);               // 3628800

• 用一个符合语义的函数去调用改写后的尾递归函数

  function tailFactorial (num, total) {
      if (num === 1) return total;
      return tailFactorial(num - 1, num * total);
  }
  function factorial (num) {
      return tailFactorial(num, 1);
  }
  factorial(5);                // 120
  factorial(10);               // 3628800

  看完了求阶乘的例子，再来看一下经典的爬楼梯问题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶100层呢？

一般递归实现：

function fn(n) {
    if (n === 1) {
        return 1;
    }
    if (n === 2) {
        return 2;
    }
    return fn(n - 1) + fn(n - 2);
}

尾递归优化：

function fn(n, n1 = 1, n2 = 2) {
    if (n === 1) {
        return n1;
    }
    if (n === 2) {
        return n2;
    }
    return fn(n - 1, n2, n1 + n2);
}

结语

在这里我们主要讨论了尾调用和尾递归。要注意的是，经过测试，Chrome 和 Firefox 并没有对尾调用进行优化，Safari 对尾调用进行了优化，Node 高版本也已经去除了通过 –harmony_tailcalls 参数启用尾调用优化，这些问题在实际使用过程中要注意，如果你有任何的问题，也欢迎评论区留言讨论。

Donate