递归算法入门：像俄罗斯套娃一样思考

用代码拆解“函数调用自己”的奇妙思维你有没有拆过俄罗斯套娃打开一个里面还有一个再打开又一个……直到最小的那个。递归Recursion就是这种“自相似”的思维方式——函数在执行过程中调用自身像一面镜子照出另一面镜子。本文会带你从零理解递归并附上可直接运行的代码示例让你真正掌握这个编程核心技巧。什么是递归递归 递推 回归递推把大问题分解成形式相同但规模更小的子问题回归子问题解决后逐层返回结果拼出原问题的答案一句话把大象装进冰箱需要几步递归的回答是1. 先放进去一只小象2. 剩下的事和之前一样。递归的两个关键要素基线条件Base Case问题小到可以直接解决不再调用自身。没有它递归会无限循环就像没有底的套娃。递归条件Recursive Case把问题拆小并调用自身去处理子问题。 经验法则写递归前先想清楚“最简单的情况是什么”再想“如何把复杂情况变简单”。经典案例阶乘n!阶乘的定义0! 1n! n × (n-1)!这本身就是递归定义。JavaScript 实现javascriptfunction factorial(n) { // 基线条件 if (n 0 || n 1) { return 1; } // 递归条件 return n * factorial(n - 1); } console.log(factorial(5)); // 120 // 执行过程 // 5 * factorial(4) // 5 * 4 * factorial(3) // 5 * 4 * 3 * factorial(2) // 5 * 4 * 3 * 2 * factorial(1) // 5 * 4 * 3 * 2 * 1 120Python 实现pythondef factorial(n): if n 1: return 1 return n * factorial(n - 1) print(factorial(5)) # 120另一个经典斐波那契数列数列0, 1, 1, 2, 3, 5, 8, 13……规律F(0)0, F(1)1, F(n)F(n-1)F(n-2)javascriptfunction fibonacci(n) { if (n 0) return 0; if (n 1) return 1; return fibonacci(n - 1) fibonacci(n - 2); } // 输出前10项 for (let i 0; i 10; i) { console.log(F(${i}) ${fibonacci(i)}); }⚠️ 这种写法简单易懂但效率极低指数级重复计算。实际开发中可用记忆化递归或循环优化。递归 vs 循环一个直观对比任务计算 1 到 n 的和循环迭代方式javascriptfunction sumLoop(n) { let total 0; for (let i 1; i n; i) { total i; } return total; }递归方式javascriptfunction sumRecur(n) { if (n 1) return 1; return n sumRecur(n - 1); }维度递归循环代码简洁度更贴近数学定义需要显式控制变量性能函数调用有开销通常更快内存风险可能栈溢出见下文可控适用场景树/图遍历、分治算法简单线性重复小心“栈溢出”递归的代价每次函数调用系统都会在“调用栈”上压入一个帧包含参数、局部变量。递归过深比如factorial(100000)会导致栈空间耗尽程序崩溃。如何避免设定合理的递归深度限制通常几千层以内安全改用尾递归优化部分语言支持用循环或显式栈重写尾递归示例仅限支持优化的环境javascript// 尾递归最后一步只调用自身不附加运算 function factorialTail(n, accumulator 1) { if (n 1) return accumulator; return factorialTail(n - 1, n * accumulator); } // 某些JS引擎如Safari会优化这种写法避免栈增长递归的威力遍历树状结构递归最擅长的就是处理未知深度、天然嵌套的数据。比如文件目录、评论回复、组织架构。示例遍历文件夹Node.jsjavascriptconst fs require(fs); const path require(path); function listAllFiles(dirPath, indent ) { const files fs.readdirSync(dirPath); for (let file of files) { const fullPath path.join(dirPath, file); const stat fs.statSync(fullPath); if (stat.isDirectory()) { console.log(${indent} ${file}); listAllFiles(fullPath, indent ); } else { console.log(${indent} ${file}); } } } listAllFiles(./my-project);递归 vs 分治一对好搭档递归是实现分治算法的自然方式分割把问题分成几个相同形式的子问题解决递归地解决子问题子问题足够小就直接解合并把子问题的结果合并成原问题的解经典案例归并排序、快速排序、二分查找。二分查找的递归写法javascriptfunction binarySearch(arr, target, left 0, right arr.length - 1) { if (left right) return -1; // 没找到 const mid Math.floor((left right) / 2); if (arr[mid] target) return mid; if (arr[mid] target) return binarySearch(arr, target, left, mid - 1); return binarySearch(arr, target, mid 1, right); } const sorted [2, 5, 8, 12, 16, 23, 38, 56]; console.log(binarySearch(sorted, 23)); // 5总结什么时候该用递归✅适合递归的场景问题天然是递归定义的如树、图、汉诺塔需要深度优先遍历如解析JSON、渲染嵌套UI组件想让代码高度贴合数学公式如阶乘、斐波那契❌不适合递归的场景只需要简单重复用循环更清晰递归深度可能超过数千小心栈溢出性能要求极高函数调用有开销动手挑战一下实现一个函数flattenArray将任意嵌套的数组展开成一维数组javascript// 输入[1, [2, [3, 4], 5], 6] // 输出[1, 2, 3, 4, 5, 6] function flattenArray(arr) { // 你的递归代码在这里 }details summary参考实现点击展开/summaryjavascriptfunction flattenArray(arr) { let result []; for (let item of arr) { if (Array.isArray(item)) { result result.concat(flattenArray(item)); } else { result.push(item); } } return result; }/details递归就像编程中的“盗梦空间”——只要你信任每一层都能完成自己的任务整个问题就会像多米诺骨牌一样优雅倒塌。希望这篇文章能帮你打开这扇思维之门。欢迎在评论区留下你对递归的理解或疑惑我会抽空回复。如果你喜欢这种带代码的技术科普别忘了点赞和关注我们下期见