一、递归函数

何为递归

• 递：一层一层的进去
• 归：一层一层的回来
• 递归函数：一个函数内部，调用了自己，循环往复

递归终点

• 当递归不设置的终点的时候，就会陷入死循环
• 设置的终点使用 return（return作用就是终止函数执行）

注意：写递归先写停 return

下面这个代码就是一个最简单的递归函数

在函数内部调用了自己，函数一执行，就调用自己一次，在调用再执行，循环往复，没有止尽

function fn() {
  fn();
}
fn();

注意：递归慎用，能用循环解决的事情，尽量别用递归

二、递归案例

2.1、需求： 求 1 至 5 的和（15）

1. 先算 1 + 2 得 3
2. 再算 3 + 3 得 6
3. 再算 6 + 4 得 10
4. 再算 10 + 5 得 15
5. 结束

写递归函数先要写结束条件（为了避免出现 “死递归”）

设置终点结束条件

function sum(n) {
  //传递进来的是1
  //当n==1的时候结束
  if (n == 1) {
    return 1;
  }
}
console.log(sum(1)); // 1

再写不满足条件的时候我们的递归处理

function sum(n) {
  //传递进来的是5
  //当n==1的时候结束
  if (n == 1) {
    return 1;
  }
  //不满足条件的时候，就是当前数字 + 比自己小 1 的数字
  return n + sum(n - 1);
}
console.log(sum(5)); // 15

2.2、递归求阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积

并且 1 的阶乘为 1

自然数 n 的阶乘写作 n!

2.2.1、例子：求 3 的阶乘（321）

3 的阶乘 =
=> 3 * 2 的阶乘
    => 2 * 1 的阶乘
        => 1 的阶乘就是 1
从上往下就是 递 的过程
从下往上就是 归 的过程

function fn(n) {
  // n 就是你要求的终点
  if (n === 1) {
    // 设置终点位置
    return 1;
  }
  // 当 n 不是 1 的时候
  // 就递进去
  return n * fn(n - 1);
}
fn(3); // 6

代码分析

第一次：
    n = 3 , if(n===1)不成立
    return 3 * fn(2)
    fn(3) = 3 * fn(2)
第二次：
    n = 2 , if(n===1)不成立
    return 2 * fn(1)
    fn(3) = 3 * fn(2)
          = 3 * 2 * fn(1)
第三次：
    n = 1 , if(n===1) 成立
    return 1
    fn(3) = 3 * fn(2)
          = 3 * 2 * fn(1)
          = 3 * 2 * 1 = 6

2.3、递归求最大公约数

最大公约数：指两个或多个整数共有约数中最大的一个

如果数 a 能被数 b 整除，a 就叫做 b 的倍数，b 就叫做 a 的约数。

约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。

2.3.1、需求分析

求最大公约数会用到辗转相除法
先确定终点：
    => a % b ===0
    => b 就是最大公约数
未到终点时：
    => 计算相对小的数字，和两个数字的余数

2.3.2、书写代码

function fn(a, b) {
  // 保证 a > b
  if (a < b) {
    var tmp = a;
    a = b;
    b = tmp;
  }
  // 设置终点
  if (a % b === 0) {
    return b;
  }
  // 未到终点
  return fn(b, a % b);
}
console.log(fn(2, 4)); // 2

2.3.3、代码分析

第一次：
    a = 2 , b = 4 , if(a < b)成立
    a = 4 , b = 2 , if(a % b === 0)成立
    return b (b = 2) 返回结果，结束递归

2.4、递归求斐波那契数列

斐波那契数列指的是这样一个数列：

1 1 2 3 5 8 13 21 34 55 …

这个数列从第3项开始，每一项都等于前两项之和

2.4.1、需求分析

=> 第一位和第二位是固定的 1
=> 第三位开始依次是前两位的和
    => 确定终点
        => n 是你要求第几位
        => 当 n 等于 1 或者 2 的时候，表示你要求第一位或者第二位
    => 没到终点之前
        => 你要求第 n 位，实际上就是 n-1 和 n-2 位的和

2.4.2、书写代码

function fn(n) {
  // n 就是要求的第 n 位
  //  设置终点
  if (n === 1 || n === 2) {
    return 1;
  }
  // 未到终点
  return fn(n - 1) + fn(n - 2);
}
console.log(fn(10)); // 55