javascript递归是什么_如何编写递归函数

幻影之瞳 2025-12-25 00:00:00 次阅读

JavaScript递归是函数调用自身解决问题的技巧，适用于树形遍历、阶乘、斐波那契等自相似结构；必须包含基础情形（终止条件）和递归情形（逐步简化参数），否则会导致栈溢出。

JavaScript递归是指函数调用自身来解决问题的编程技巧。它适合处理具有自相似结构的问题，比如遍历树形数据、计算阶乘、斐波那契数列、解析嵌套对象或数组等。写递归函数的关键是：明确**终止条件**（base case）和**递归逻辑**（recursive case），否则会陷入无限调用导致栈溢出。

递归函数的两个必要部分

每个有效的递归函数都必须包含：

基础情形（Base Case）：不调用自身的出口条件，防止无限循环。例如计算阶乘时，0! = 1 或 1! = 1 就是基础情形。
递归情形（Recursive Case）：函数调用自身，但传入更小或更简化的参数，逐步逼近基础情形。例如 n! = n × (n−1)!。

一个经典例子：计算阶乘

下面是用 JavaScript 编写的阶乘递归函数：

function factorial(n) {
  // 基础情形：0! 和 1! 都等于 1
  if (n === 0 || n === 1) {
    return 1;
  }
  // 递归情形：n! = n × (n-1)!
  return n * factorial(n - 1);
}

调用 factorial(4) 的执行过程是：
factorial(4) → 4 × factorial(3) → 4 × 3 × factorial(2) → 4 × 3 × 2 × factorial(1) → 4 × 3 × 2 × 1 = 24

常见陷阱与注意事项

写递归容易出错，需特别注意：

忘记或写错基础情形：会导致“Maximum call stack size exceeded”错误。
递归参数未向基础情形靠近：比如本该减 1 却加 1，或没更新参数，也会无限调用。
性能问题：某些递归（如朴素斐波那契）存在大量重复计算，可用记忆化（memoization）或改用迭代优化。
深嵌套可能触发调用栈限制：浏览器中通常限制在几千层，超深结构建议用循环+栈模拟。

实际应用：遍历嵌套对象

比如把一个含 children 数组的菜单对象扁平化：

function flattenMenu(menu) {
  const result = [];
  for (const item of menu) {
    result.push({ id: item.id, name: item.name });
    if (Array.isArray(item.children) && item.children.length > 0) {
      result.push(...flattenMenu(item.children)); // 递归处理子菜单
    }
  }
  return result;
}

这个函数对每一层的 children 都调用自身，自然覆盖任意深度的嵌套结构。