image.png

递归**是一种解决问题的方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归作为一种算法在程序设计语言中广泛应用，通常涉及函数调用自身。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归函数

如果一个函数在内部调用自身，这个函数就是递归函数：

  1. function recursiveFuntion(params) {
  2.     recursiveFuntion(parmas);
  3. }

或者在另一个函数内间接调用自身，这个函数也是递归函数：

  1. function recursiveFuntion1(params) {
  2.   recursiveFuntion2(params);
  3. }
  5. function recursiveFuntion2(params) {
  6.   recursiveFuntion1(params);
  7. }

栈溢出

每一个递归函数都必须有一个停止递归调用的条件以防止栈溢出。在计算机中，函数调用时通过 栈 这种数据结构来实现的，每当进入一个函数调用，栈就会加一层栈帧，没当函数返回，栈就会减一层栈帧，栈的大小不是无限的，如果递归调用次数过多，就会导致栈溢出。

计算一个数的阶乘

我们来看看如何使用递归计算一个数的阶乘。数 n 的阶乘，定义为 n! ，表示从 1 到 n 的整数的乘积。

例如 5 的阶乘表示为 5!，和 5 × 4 × 3 × 2 × 1 相等，结果是 120。

使用函数 factorial(n) 表示计算数 n 的阶乘，
可以将其步骤定义如下：(n) * (n - 1) * (n - 2) * (n - 3) * ... * 1，
也就是 factorial(n) = n! = (n) (n - 1) (n - 2) (n - 3) … 1 = (n - 1)! n = factorial(n - 1) n ，
所以， factorial(n) 可以表示为 n factorial(n - 1)，只有 n = 1 或 n = 0 时需要特殊处理。

使用递归的 factorial 函数定义如下：

  1. const factorial = (n) => {
  2.     if (n === 1 || n === 0) { // 停止递归调用的条件
  3.     // 1! = 1 x 0!，0! 也等于1，因此 n === 1 或 n === 0 时，直接返回 1
  4.       return 1;
  5.   }
  7.   return n * factorial(n - 1); // 递归调用
  8. }

解决递归调用栈溢出的方法是通过 尾递归 优化，尾递归是指，在函数返回的时候，调用自身，并且 return 语句不能包含表达式。

上面的 factorial 函数由于 return n * factorial(n - 1); 引入了乘法表达式，所以就不是尾递归了。我们改写上面的递归函数，再提供一个尾递归函数，将每一步的乘积传入到尾递归函数中：

  1. const tailFactorial = (n, total) => {
  2.   if (n === 1 || n === 0) return total;
  3.   return tailFactorial(n - 1, n * total);
  4. }
  6. const factorial = (n) => {
  7.     return tailFactorial(n, 1);
  8. }

我们还可以使用ES6的函数默认值来简化代码：

  1. const factorial = (n, total = 1) {
  2.     if (n === 1 || n ===0) return total;
  3.   return factorial(n - 1, total);
  4. }

递归求斐波那契数

斐波那契数列是一个由 0、1、1、2、3、5、8、13、21、34、…… 等数组成的序列。数 2 由 1 + 1 得到，数 3 由 1 + 2 得到，以此类推。斐波那契数列的定义如下：

  • 位置 0 的斐波那契数是 0
  • 位置 1 和 2 的斐波那契数是 1
  • 位置 n (此处 n>2) 的斐波那契数是位置 (n-1) 的斐波那契数加上位置 (n-2) 的斐波那契数

在数学上，斐波那契数列以递归的方式来定义：

  • F(0)=0
  • F(1)=1,
  • F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

使用非尾递归的方式求斐波那契数，代码如下：

  1. const fibonacci = (n) => {
  2.     if (n < 1) return 0;
  3.   if (n <= 2) return 1;
  4.   return fibonacci(n-1) + fibonacci(n-2);
  5. }

使用尾递归优化后的 fibonacci 求斐波那契数实现如下：

  1. const fibonacci = (n, ac1 = 1, ac2 = 1) => {
  2.     if (n < 1) return 0;
  3.   if (n <= 2) return 1;
  4.   return fibonacci(n - 1, ac2, ac1 + ac2);
  5. }

小结

使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。
递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令，所有的循环都用递归实现，这就是为什么尾递归对这些语言极其重要。对于其他支持”尾调用优化”的语言（比如Lua，ES6），只需要知道循环可以用递归代替，而一旦使用递归，就最好使用尾递归。

参考资料：
书籍：
《学习JavaScript数据结构与算法》
文章：
http://www.ruanyifeng.com/blog/2015/04/tail-call.html
https://www.liaoxuefeng.com/wiki/1016959663602400/1017268131039072
https://segmentfault.com/a/1190000020694801