定义

程序自己调用自己的方法就叫 递归。

递归，在我的理解当中，就是 关系还没决裂之前，有来有往 。

  1. 关系决裂，就是断掉递归的条件，如下面阶乘递归实现中的 if 语句
  2. 有来，也就是有递进的关系，有一个规律的关系层层递进，如下面阶乘递归实现中的 n*f(n-1)
  3. 有往，就是 return ，只有 return 回去才能让结果完整。

这三个条件缺一不可。

阶乘递归

  1. function factorial(n) {
  2.     if (n <= 1) return n;
  4.     return n * factorial(n - 1);
  5. }
  7. console.log(factorial(5));

斐波那契数列

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

  1. 位置0的数值是0
  2. 位置1和2的数值都是1
  3. n的值都是 (n-1) + (n-2) 的和
  1. function fibonacci(n) {
  2.     return n <= 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
  3. }
  5. console.log(fibonacci(5))

这里需要特别注意的是，这个函数求的是第n个斐波那契数是什么，而不是n之前的所有斐波那契数的和

普通循环优化

递归的性能其实并不好，特别是在计算斐波那契数时，如果你上面的函数n输入为100，页面将会直接卡死，所以，递归的实现看起来是比较优雅，但在大计算量的时候，还得慎重，这里提供一个普通循环实现的斐波那契数列实现。

  1. function fibonacciIterative(n) {
  2.     if (n < 1) return 0;
  3.     if (n <= 2) return 1;
  4.     let fibNMinus2 = 0;
  5.     let fibNMinus1 = 1;
  6.     let fibN = n;
  7.     for (let i = 2; i <= n; i++) { // n >= 2
  8.         fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
  9.         fibNMinus2 = fibNMinus1;
  10.         fibNMinus1 = fibN;
  11.     }
  12.     return fibN;
  13. }

输出n位斐波那契数

  1. function printFibonacci(n) {
  2.     if (n <= 0) return;
  4.     let result = [];
  6.     for (i = 0; i < n; i++) {
  7.         if (i <= 1) {
  8.             result.push(i);
  9.         } else {
  10.             result.push(result[i - 1] + result[i - 2]);
  11.         }
  12.     }
  14.     return result;
  16. }
  18. console.log(printFibonacci(5))

尾递归

尾调用

讲尾递归之前，需要先了解 尾调用 。

尾调用，是指一个函数最后的返回是一个函数的调用。如：

  1. function f(x){
  2.     return g(x);
  3. }
  5. // 不是尾调用
  6. function f(x){
  7.     g(x);
  8. }
  10. // 不是尾调用
  11. function f(x){
  12.     return g(x) + 1;
  13. }

如上代码，调用完 g(x) 之后没有返回，或者还有其他运算，都不算尾调用。
那么，在递归中的尾调用，则就是尾递归。

尾递归阶乘

  1. function factorial(n, total = 1) {
  2.     if (n <= 1) return total;
  3.     return factorial(n - 1, n * total);
  4. }
  5. console.log(factorial(3));

尾递归斐波那契数列

  1. 'use strict'
  2. function fibonacci(n, current = 0, next = 1) {
  3.     if (n === 1) return next;
  4.     if (n === 0) return 0;
  5.     return fibonacci(n - 1, next, current + next);
  6. }
  8. console.log(fibonacci(100))

如何将递归改写为尾递归

尾递归的核心就是：最后返回的直接是函数的调用。所以，把原本在最后调用递归后还有的运算，通过传参的方式进行传递，从而优化掉递归后的运算，从而实现尾递归。
一般从一开始就写出完美的尾递归比较有难度，可以先按正常实现递归，在慢慢优化。

参考