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); }
