递归

常见的算法思维：

1. 分治法
2. 迭代法
3. 枚举法
4. 回溯法
5. 贪心算法
6. 动态规划

递归是典型的分治的思想。

🙋什么是递归？

回答：一种特殊形式的调用形式，指的是函数自己调用自己的形式。

递归代码示例：

function a(){
  a();
}
a();

上面的代码就是一个递归的例子，只不过该例子是一个死递归。

为什么觉得难☹️

因为递归属于函数式编程，函数式编程是另外一种编程范式。大家平时习惯的是命令式编程。

因为编程范式不一样，有些核心的思想都不同了。例如在函数式编程里面，常见概念：纯函数（没有副作用的函数）、高阶函数、不可变数据、递归....

书写递归诀窍

1. 委托的思想：一个递归函数，告诉你是什么功能，你就不要想内部怎么实现的，反正委托给它，它就能给你正确的结果。
2. 设计出口：什么时候是递归的终点，一旦没有设计出口，就会变成死递归。

求 n 的阶乘：n * (n - 1) * (n-2) * ... * 1

5! = 5 * 4 * 3 * 2 * 1

5! ---> 5 * 4!
4! ---> 4 * 3!
3! ---> 3 * 2!
2! ---> 2 * 1!
1! ---> 1(出口)

f(n); // 返回 n 的阶乘

function f(n){
  // 出口非常重要，不会再继续往下调用了。
  if(n === 1){
    return 1;
  }
  return n * f(n-1);
}

  function addPlus(index1, index2) {
      if(index1 === index2) {
          return index1
      } else {
          return addPlus(index1 + 1, index2) + index1
      }
  }

上边两个例子，我的思考过程就是先找出口，以第二个阶加为例，我要想它是怎么加的，例如从3加到5，我从3开始加就是3+4+5，那么我要让第一个参数每运行一次加一，当第一个参数等于第二个参数的时候就结束了，返回第一个参数，这样出口条件就有了，然后就是怎么加，首先从第一个参数加到第二个参数，那就要从第一个参数开始加，先写个 index1 + ，他要加什么呢，他要加的是index + 1，那么第二个参数就有了addPlus(index1 + 1, index2)，这里其实是把第二个参数当作了基准

课堂练习

1. 斐波那契数列

0 1 1 2 3 5 8 13 21...

// 求出指定位数的斐波那契数
f(1) ---> 0
f(5) ---> 3
f(位数) ---> 对应位数的斐波那契数

function f(n){
  // 设计出口
  if(n === 1){
    return 0;
  } else if(n === 2){
    return 1;
  } else {
    return f(n-1) + f(n-2);
  }
}

2. 实现一个 sum 函数，该函数接收 2 个参数，返回从第一个参数加到第二个参数的和。

sum(1, 100) ---> 1 + 2 + 3 + 4 + ... + 99 + 100
sum(1, 99) ---> 返回从 1 加到 99 的和

• 委托的思想：假设传入的是 1 和 100，计算从 1 加到 100，从 1 加到 100 等价于 100 + 1 加到 99 的和，从 1 加到 99 等价于 99 + 从1 加到 98
• 设计出口：出口就是两个数相等的时候，例如从 1 加到 1，返回的就是 1；从 50 加到 50，返回的就是 50

function sum(m, n){
  if(m === n){
    return m;
  }
  return n + sum(m, n - 1);
}

-EOF-