17370845950

递归函数需满足三个必要要素：基础情形（终止条件）、递归情形（拆解为更小同类问题）、参数推进（确保趋近终止）。缺一不可，否则易栈溢出或逻辑错误。

递归函数的本质：函数调用自己

递归不是某种高级技巧，它只是函数在定义或执行过程中直接或间接调用自身的一种写法。关键在于：必须有明确的终止条件（base case），否则会无限调用导致 RangeError: Maximum call stack size exceeded。

怎么写一个安全的递归函数：三个必要要素

缺一不可，漏掉任意一个都容易崩：

• 基础情形（base case）：决定何时停止递归，通常是最简单、可直接返回结果的输入，比如 n === 0 或 array.length === 0
• 递归情形（recursive case）：把当前问题拆成“更小的同类问题”，并用函数自身去解决它，比如 factorial(n - 1)
• 参数推进（progress）：每次递归调用必须让参数朝 base case 靠拢，否则就是死循环

例如计算阶乘：

function factorial(n) {
  if (n < 0) return NaN;           // 边界防护
  if (n === 0 || n === 1) return 1; // base case
  return n * factorial(n - 1);      // recursive case，n 每次减 1，向 0 靠拢
}

什么时候该用递归？哪些场景容易翻车

适合递归的问题通常具有「自相似结构」：树遍历、嵌套对象扁平化、深度克隆、分治算法（如快排）、括号匹配等。但要注意：

立即学习“Java免费学习笔记（深入）”；

• 浏览器环境下，深层递归（>10000 层）大概率触发栈溢出；Node.js 默认栈大小也有限
• 递归天然比循环多开销：每次调用要压栈、保存上下文、返回时弹栈
• 不是所有递归都能轻松转成循环，但多数能 —— 如果性能敏感或数据深度不可控，优先考虑迭代 + 显式栈（Array 模拟）
• ES2015+ 支持尾调用优化（TCO），但仅限严格模式且只有 Safari 实现了，Chrome/Firefox 均未启用，return factorial(n - 1) 这种纯尾调用也不能指望自动优化

常见错误：你以为在递归，其实没返回值

最隐蔽的坑：忘记在递归分支里写 return，导致函数静默返回 undefined，后续计算全错。

错误示例（查找嵌套对象中的某个 key）：

function findKey(obj, target) {
  if (obj && typeof obj === 'object') {
    if (target in obj) return obj[target];
    for (let key in obj) {
      findKey(obj[key], target); // ❌ 缺少 return！这里的结果被丢弃了
    }
  }
}

正确写法：

function findKey(obj, target) {
  if (obj && typeof obj === 'object') {
    if (target in obj) return obj[target];
    for (let key in obj) {
      const result = findKey(obj[key], target);
      if (result !== undefined) return result; // ✅ 显式检查并返回
    }
  }
}

递归的复杂点不在语法，而在逻辑流向是否真正收敛 —— 每一层调用是否真的参与最终结果，这点比写对 base case 还容易被忽略。