递归：从求和问题到数组扁平化，彻底搞懂递归思维

文章目录前言一、如何求 123…n 的和1.1 迭代解法1.2 自顶向下递归思维二、递归三要素重点三、调用栈机制 栈溢出风险3.1 压栈与出栈3.2 栈溢出四、数组扁平化递归实战4.1 原生 flat() 回顾4.2 递归手写基础版4.3 升级版支持深度控制五、性能优化 避坑5.1 concat 的性能问题六、全文总结七、核心知识点复盘八、常见问题 避坑指南前言递归用「自己调用自己」将复杂问题拆为规模更小的同类子问题代码比迭代更简洁、更贴近问题本质。本文从「求 12…n 的和」切入深入到「数组扁平化」的工程实战覆盖递归三要素、调用栈机制、尾调用优化、多方案实现及面试避坑。一、如何求 123…n 的和1.1 迭代解法functionsum(n){lettotal0;for(leti1;in;i)totali;returntotal;}迭代靠循环变量逐个累加直观但没揭示问题的结构。1.2 自顶向下递归思维换一个角度思考——大问题和小问题之间的关系sum(5) sum(4) 5 sum(4) sum(3) 4 sum(3) sum(2) 3 sum(2) sum(1) 2 sum(1) 1 ← 终止画成树状结构就是自顶向下展开、自底向上回归sum(5) / \ sum(4) 5 / \ sum(3) 4 / \ sum(2) 3 / \ sum(1)2 | 1核心洞察sum(n)sum(n-1)n一直拆到sum(1)1这个「原子问题」为止。二、递归三要素重点任何一个正确的递归函数必须同时满足三个要素要素含义本例① 递归公式大问题如何由小问题构成f(n) f(n-1) n② 退出条件递归终止的 Base Casef(1) 1③ 子问题结构一致每次递归问题类型不变只缩小规模sum(n-1)和sum(n)同构代码实现functionsum(n){if(n1)return1;// ② 退出条件returnsum(n-1)n;// ① 递归公式 ③ 子问题结构一致}console.log(sum(100));// 5050忘记写 base case 无限递归 栈溢出面试直接挂。三、调用栈机制 栈溢出风险3.1 压栈与出栈以sum(3)为例压栈拆解 sum(3) 入栈 → sum(2) 入栈 → sum(1) 入栈 → 命中 base case返回 1 出栈回归 sum(1) 返回 1 → sum(2): 123 → sum(3): 336每一层递归保留独立的局部变量调用栈天然提供隔离。3.2 栈溢出JS 引擎调用栈约 1 万层上限sum(100000)直接报错RangeError: Maximum call stack size exceeded递归的空间复杂度 O(n)每一层都占栈内存迭代只用 O(1)。数据量大时优先迭代。四、数组扁平化递归实战4.1 原生flat()回顾constarr[1,[2,[3,4,[5,6]]]];arr.flat();// [1, 2, [3, 4, [5, 6]]] 默认一层arr.flat(2);// [1, 2, 3, 4, [5, 6]] 指定深度arr.flat(Infinity);// [1, 2, 3, 4, 5, 6] 全部拍平4.2 递归手写基础版思路跟求和一致是数组就递归深入不是数组就放入结果。constflatten(arr){letresult[];arr.forEach((item){if(Array.isArray(item)){resultresult.concat(flatten(item));// 递归拍平 拼接}else{result.push(item);// base case}});returnresult;};constarr[1,2,[3,4,[5,6]]];console.log(flatten(arr));// [1, 2, 3, 4, 5, 6]关键步骤Array.isArray(item)是分岔口concat合并子结果push收拢非数组元素。4.3 升级版支持深度控制constflattenDepth(arr,depth1){letresult[];arr.forEach((item){if(Array.isArray(item)depth0){resultresult.concat(flattenDepth(item,depth-1));// depth 递减}else{result.push(item);}});returnresult;};constarr[1,[2,[3,4,[5,6]]]];console.log(flattenDepth(arr,1));// [1, 2, [3, 4, [5, 6]]]console.log(flattenDepth(arr,2));// [1, 2, 3, 4, [5, 6]]console.log(flattenDepth(arr,Infinity));// [1, 2, 3, 4, 5, 6]核心技巧depth 0作为额外退出条件每深入一层depth - 1。Infinity - 1 Infinity所以传Infinity等价全部拍平。五、性能优化 避坑5.1concat的性能问题concat每次创建新数组并全量拷贝嵌套深时开销可观。替代// 方案 A展开运算符result.push(...flatten(item));六、全文总结从「求 1~n 的和」建立递归三要素框架图解调用栈压栈/出栈过程再迁移到「数组扁平化」实战给出基础版、深度控制版、方案及性能分析覆盖递归思维的全链路。七、核心知识点复盘知识点要点递归三要素递归公式 / 退出条件 / 子问题结构一致调用栈压栈拆解 出栈回归每层独立局部变量栈溢出约 1 万层上限大纵深用迭代flat(depth)depth默认 1Infinity全部拍平深度控制depth - 1逐层递减depth 0停止尾调用优化递归是函数最后一步才可复用栈帧V8 未全面支持迭代兜底手动stack数组模拟调用栈突破引擎限制八、常见问题 避坑指南Q1递归和迭代怎么选优先迭代问题具有清晰递归结构树遍历、分治且数据可控时用递归——代码更贴近问题定义。Q2concatvspush(...)哪个好小数据没差别中数据用push(...)减少中间数组大数据用for逐项push避免展开运算符参数上限。Q3递归如何调试第一行打console.log看入参 → 优先检查 base case90% 的 bug 在此→ 小数据验证后再跑真实数据。Q4为什么用Array.isArray而不是instanceof Array跨 iframe / 跨 realm 场景下instanceof会误判Array.isArray永远正确。Q5手写 flat 最容易漏什么忘记depth默认值应为1不是Infinity在原数组上直接splice产生副作用空数组边界处理遗漏。递归不是魔法是将「大问题」映射到「同类小问题」的思维方式。掌握三要素、理解调用栈、知道何时迭代兜底——你就真正掌握了递归的精髓。