1. 什么是递归

函数内部调用自己，这就是递归

2. 为什么用递归

对数据进行处理，优化处理流程可以用递归

3. 构成递归三要素（必须）

3.1 参数递归逻辑：如下例，demo(n-1)对比 demo(n)参数递归逻辑为 n-1

3.2 临界值：如下例，n == 0，不再递归

3.3 递归业务逻辑：如下例，n + demo(n-1)，0 到 n 求和

// 例子
function demo(n) {
  if (n == 0) return 0;
  return n + demo(n - 1);
}

4. 经典递归案例

// 4.1：0 到 n 求和
function sum(n) {
  // sum(n-1) n-1 为参数递归的逻辑
  // n == 1 为临界值
  // n + sum(n-1) 为递归业务逻辑

  if (n == 1) return 1;
  return n + sum(n - 1);
}
sum(100); // 5050

// 4.2：数组扁平化
// 将[1, [2, 3], [4, [5, 6]], 7]转换为[1, 2, 3, 4, 5, 6, 7]
function flattenArray(arr) {
  // arr.forEach(item => { flattenArray(item) }) 数组遍历的item，为参数递归的逻辑
  // !Array.isArray(item) 不是数组时，为临界值
  // resultArr.push(...flattenArray(item)) 将数组拼接起来， 为递归业务逻辑

  const resultArr = [];
  arr.forEach((item) => {
    if (!Array.isArray(item)) {
      resultArr.push(item);
    } else {
      resultArr.push(...flattenArray(item));
    }
  });
  return resultArr;
}
flattenArray([1, [2, 3], [4, [5, 6]], 7]); // [1, 2, 3, 4, 5, 6, 7]

// 4.3：深拷贝
function deepClone(obj) {
  // for (const key in obj) { deepClone(obj[key]) } 遍历的obj[key]，为参数递归的逻辑
  // typeof v === "object" && v !== null 是对象类型且不为null继续递归，反之则为临界值
  // target[key] = deepClone(v) 为递归业务逻辑

  // 拷贝数据不是对象类型直接返回
  if (typeof obj !== "object") return obj;
  const target = Array.isArray(obj) ? [] : {};
  for (const key in obj) {
    // 判断数据中key是否重复，不重复着继续逻辑
    if (!hasOwnProperty.call(obj, key)) continue;
    const v = obj[key];
    target[key] = typeof v === "object" && v !== null ? deepClone(v) : v;
  }
  return target;
}

// 4.4：斐波拉契数列
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...求第 n 项
function fib(n) {
  // fib(n-1)，fib(n-2) 第n位数为第n-1位数+第n-2位数，n-1，n-2为参数递归的逻辑
  // n == 1 || n == 2 第1位数为1，第二位数为1，n==1，n==2为临界值
  // fib(n-1) + fib(n-2) 第n位数为第n-1位数+第n-2位数，为递归业务逻辑

  if (n == 1 || n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

// 4.5：爬楼梯
// 一个人爬楼梯，只可以一步走1层或一步走2层，到达n层，一共多少种走法？
// 1, 2, 3, 5, 8; 爬1层1种走法，2层2种，3层3种，4层5种，5层8种，...n层n-1层+n-2层走法
function climbStairs(n) {
  // n-1，n-2 为参数递归的逻辑
  // n == 1 || n ==2 为临界值
  // climbStairs(n-1) + climbStairs(n-2) 为递归业务逻辑

  if (n == 1 || n == 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}