17370845950

递归是函数调用自身解决问题的技巧，需满足基础情况（终止条件）和递归情况（规模递减），典型步骤为确定base case、找出递推关系并编码实现，常见陷阱包括缺失base case或未缩小问题规模。

递归是函数调用自身来解决问题的编程技巧，核心在于把大问题拆成结构相同但规模更小的子问题，直到遇到可以直接解决的“基础情况”（base case）。

递归的两个必要条件

一个正确的递归函数必须同时满足：

• 基础情况（Base Case）：明确的终止条件，防止无限调用。比如计算阶乘时，0! = 1 或 1! = 1 就是基础情况。
• 递归情况（Recursive Case）：函数调用自身，且每次调用都要让问题规模变小（例如参数减小、数组缩短），逐步逼近基础情况。

写递归函数的典型步骤

以计算 n 的阶乘（n!）为例：

• 想清楚“最小输入是什么？结果已知吗？”→ 确定 base case：if (n === 0 || n === 1) return 1;
• 想清楚“n 的阶乘和 (n−1) 的阶乘有什么关系？”→ 找出递推关系：n! = n × (n−1)!
• 把关系翻译成代码：在 base case 外返回 n * factorial(n - 1)

function factorial(n) {
  if (n === 0 || n === 1) return 1; // base case
  return n * factorial(n - 1);      // recursive case
}

常见陷阱与注意事项

递归容易出错，尤其新手常忽略这些细节：

• 忘记或写错 base case → 导致栈溢出（RangeError: Maximum call stack size exceeded）
• 递归调用没缩小问题规模 → 比如写成 factorial(n) 而不是 factorial(n - 1)，也会无限调用
• 深层递归可能影响性能或触发调用栈限制 → 大数据量时考虑是否改用循环，或使用尾递归优化（需引擎支持且写法严格）
• 递归不等于“多层嵌套” —— 关键是“自己调自己”，不是调别的函数，哪怕调了三次也是普通调用

适合用递归的实际场景

结构天然具有自相似性的问题最适用递归：

• 遍历树形结构（如 DOM 节点、文件目录、JSON 嵌套对象）
• 处理分治类算法（如快速排序、归并排序、二分查找）
• 回溯问题（如八皇后、全排列、路径搜索）
• 数学定义本身就是递归的（斐波那契数列、汉诺塔、组合数 C(n,k)）