递归本质上也是一种函数循环，在函数里对自身的一种调用，在一些常用的数据结构二叉树、图等会用到递归进行遍历、搜索，本节讲的是在普通递归基础之上的尾递归优化。

在 “Nodejs技术栈” 交流群上有童鞋提到在之前面试中有被问到 “尾递归” 这一问题，另外之前也刚写过二叉搜索树，用到了大量的递归来实现，所以也顺便讲解下什么是尾递归相比普通的递归调用有什么优势。

什么是尾递归呢？

调用者在调用一个递归函数并取得返回值之后，不在进行其它计算，直接返回！有什么好处呢？

“在程序运行时，计算机会为应用程序分配一定的内存空间；应用程序则会自行分配所获得的内存空间，其中一部分被用于记录程序中正在调用的各个函数的运行情况，这就是函数的调用栈。常规的函数调用总是会在调用栈最上层添加一个新的堆栈帧（stack frame，也翻译为“栈帧”或简称为“帧”），这个过程被称作“入栈”或“压栈”（意即把新的帧压在栈顶）。当函数的调用层数非常多时，调用栈会消耗不少内存，甚至会撑爆内存空间（栈溢出）[1]，造成程序严重卡顿或意外崩溃。尾调用的调用栈则特别易于优化，从而可减少内存空间的使用，也能提高运行速度。[1]其中，对尾递归情形的优化效果最为明显，尤其是递归算法非常复杂的情形。—— 维基百科”

看完这些概念会很晦涩，还是难以理解，下面让我们通过一个简单的阶乘例子彻底弄清楚它。

求 N 的阶乘

任何大于 1 等于 1 的自然数阶乘公式为：n! = 1 2 3 * (n -1)n

普通的递归调用

下面这个例子中，拿到尾部 factorial() 返回值之后没有直接返回，而是又做了一次乘法运算，那么这就不是一个尾递归。

  1. function factorial(n) {
  2.     if (n === 1) {
  3.         return n;
  4.     }
  6.     return n * factorial(n - 1) // 重点在尾部调用返回
  7. }
  9. console.log(factorial(5)) // 120

它的执行过程如下所示：

  1. factorial(5)
  2. 5 * factorial(5 - 1)
  3. 5 * 4 * factorial(4 - 1)
  4. 5 * 4 * 3 * factorial(3 - 1)
  5. 5 * 4 * 3 * 2 * factorial(2 - 1)
  6. 5 * 4 * 3 * 2 * 1
  7. 5 * 4 * 3 * 2
  8. 5 * 4 * 6
  9. 5 * 24
  10. 120 // 结果

尾递归优化

我们使用了 ES6 函数默认值，是为了 factorial() 初次调用时仅传入一个值，代码示例如下：

  1. function factorial(n, total = 1) {
  2.     if (n === 1) {
  3.         return total;
  4.     }
  6.     return factorial(n - 1, total * n); // 重点在尾部调用返回
  7. }
  9. console.log(factorial(5)) // 120

上面这种就是尾递归调用的写法，在拿到 factorial(n - 1, total * n) 返回值后，直接返回！
它的执行过程如下所示：

  1. factorial(5)
  2. factorial(4, 5)
  3. factorial(3, 20)
  4. factorial(2, 60)
  5. factorial(1, 120)

通过上面普通递归、尾递归优化之后的执行过程分析也很清晰了，优化之前的递归调用它的调用链条会不断的加强，相比优化之后的会更消耗资源。

Reference