前端 js 经典：递归

递归"/>

前端 js 经典：递归

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