17370845950

递归函数必须有明确终止条件，每次调用须向该条件收敛，否则栈溢出；需处理边界（如负数）、改变参数、注意JS无尾递归优化及阶乘示例的局限性。

递归函数必须有明确的终止条件

递归不是“函数调自己”就完事，关键在于每次调用都要向终止状态靠近，否则会无限执行直到栈溢出。常见错误是忘记写 return，或终止条件写成 if (n === 0) 却没处理负数输入，导致 n 永远减不到 0。

• 终止条件通常对应问题的最简子情况（比如数组长度为 0、数字为 1 或 0）
• 递归调用必须改变至少一个参数值，且该变化要朝终止条件收敛
• JavaScript 默认没有尾递归优化（TCO），深度过大（一般 >10000 层）必然报错 RangeError: Maximum call stack size exceeded

阶乘函数是最典型的递归入门示例

它直观展示“问题分解 + 终止判断 + 自调用”的三要素，但要注意它不处理非正整数输入，实际使用需加固。

function factorial(n) {
  if (n < 0 || !Number.isInteger(n)) {
    throw new Error('n must be a non-negative integer');
  }
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

• factorial(5) 展开为 5 * factorial(4) → 5 * 4 * factorial(3) → … → 5 * 4 * 3 * 2 * 1
• 每层调用都压入调用栈，返回时逐层计算乘积
• 若传入 factorial(-1)，n - 1 会越来越小，永远无法触发 n === 0，最终栈溢出

遍历嵌套对象或数组时递归比循环更自然

当结构深度不确定（如菜单树、JSON Schema、DOM 子节点），递归能避免手动维护栈或队列，逻辑更贴近数据本身。

function deepFind(obj, key) {
  if (obj === null || typeof obj !== 'object') return undefined;
  if (key in obj) return obj[key];
  for (const val of Object.values(obj)) {
    const result = deepFind(val, key);
    if (result !== undefined) return result;
  }
  return undefined;
}

• 这个函数会进入任意层级的嵌套对象或数组（因为 Object.values() 对数组也返回元素值）
• 没有显式计数器或索引变量，靠函数自身调用推进遍历
• 注意：若对象存在循环引用（比如 a.b = a），此函数会无限递归，生产环境需用 WeakMap 记录已访问对象

递归 vs 迭代：性能和可读性常要权衡

递归代码简洁、符合人类对“分而治之”的直觉，但每次调用都有栈帧开销；迭代虽略冗长，却可控、无栈溢出风险。

• 简单线性问题（如斐波那契、阶乘）用迭代更稳妥：for 循环无调用开销，空间复杂度 O(1)
• 树形/图状结构（如文件系统遍历、AST 处理）递归更易写对，强行转迭代需手动模拟栈，反而易错
• 想用递归又怕栈溢出？可改用“递归 + 异步分片”，比如用 setTimeout 或 queueMicrotask 把深层调用拆到多个任务中

真正难的不是写出第一个递归函数，而是判断某个问题是否适合递归、何时该收手改用迭代、以及怎么防住循环引用和非法输入——这些地方不加检查，上线后出问题往往悄无声息。