JavaScript递归基础：从阶乘到斐波那契数列的实现

一、递归的核心机制：基线条件与递推关系

初学者在初次接触递归时，往往容易陷入“不断调用自身无从收尾”的思维死循环中。要准确掌握递归，首先需要将其拆解为两个不可或缺的核心支柱：基线条件（Base Case）与递归推进（Recursive Step）。

• 基线条件（终止阀门）：函数中首先执行的条件分支。当传入的参数满足特定边界时，直接计算或返回已知常量，不再发起任何后续递归调用。没有基线条件，程序便无法自行终止。
• 递归推进（规模递减）：将当前问题拆解为参数更小的一项或多项子调用。递推的核心法则在于：每一次递归调用的传参，都必须在逻辑上更贴近基线条件。

在底层机制上，JavaScript 引擎使用调用栈（Call Stack）来跟踪每个函数的执行上下文。当一个函数调用自身时，引擎会为该次调用分配一个新的栈帧（Stack Frame），压入调用栈顶部，保存当前的局部变量和执行指针；只有当深层子函数返回结果后，当前栈帧才会出栈并恢复执行。

二、线性递归实践：阶乘函数的逐步实现与执行追踪

阶乘（Factorial，记作 n!）是理解单分支线性递归的绝佳案例。数学上，一个正整数 n 的阶乘被定义为所有小于等于 n 的正整数的乘积，即 n! = n × (n - 1) × ... × 1，且约定 0! = 1。

用递归思路拆解阶乘，可以得到极其纯粹的递推公式：

• 基线条件：当 n === 0 或 n === 1 时，结果确定为 1。
• 递归推进：当 n > 1 时，factorial(n) = n × factorial(n - 1)。

1. 完整代码实现

/**
 * 计算非负整数 n 的阶乘
 * @param {number} n
 * @returns {number}
 */
function factorial(n) {
  // 参数前置防错校验
  if (!Number.isInteger(n) || n < 0) {
    throw new Error("输入参数必须为非负整数");
  }

  // 1. 基线条件 (Base Case)
  if (n === 0 || n === 1) {
    return 1;
  }

  // 2. 递归推进 (Recursive Step)
  return n * factorial(n - 1);
}

// 验证输出
console.log(factorial(4)); // 示例输出: 24
console.log(factorial(0)); // 示例输出: 1

2. 执行追踪：factorial(4) 的双阶段生命周期

理解递归不能只看代码表面，必须观察函数在调用栈中的展开与收敛。以 factorial(4) 为例，其执行完整经历两个独立阶段：

1. 递进展开阶段（压栈）： factorial(4) 挂起等待 4 × factorial(3)；接着 factorial(3) 挂起等待 3 × factorial(2)；factorial(2) 挂起等待 2 × factorial(1)。此时栈深达到最大。
2. 回溯归约阶段（弹栈计算）： factorial(1) 触碰基线直接返回 1；factorial(2) 恢复计算 2 × 1 = 2 并弹出；factorial(3) 恢复计算 3 × 2 = 6 并弹出；最后 factorial(4) 计算 4 × 6 = 24 完成并输出。

三、树形分支递归：斐波那契数列与指数级重叠子问题

阶乘是典型的“单线推进”，每一次函数执行只会触发一次内部递归。而当问题演进为“多路分支”时，递归的结构复杂度将发生质的改变。最典型的模型就是斐波那契数列（Fibonacci Sequence）。

斐波那契数列定义如下：

• F(0) = 0，F(1) = 1（两个基线条件）
• F(n) = F(n - 1) + F(n - 2)，其中 n ≥ 2

1. 朴素递归实现

/**
 * 朴素递归实现斐波那契数列
 * @param {number} n
 * @returns {number}
 */
function fibonacci(n) {
  if (!Number.isInteger(n) || n < 0) {
    throw new Error("输入参数必须为非负整数");
  }

  // 基线条件
  if (n === 0) return 0;
  if (n === 1) return 1;

  // 双路分支递归
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 示例输出: 8

2. 为什么朴素递归在规模增大时会卡死？

上述代码在逻辑上极其清晰，但在计算机运行时却隐藏着极具破坏性的性能陷阱。尝试在浏览器控制台中运行 fibonacci(45)，页面通常会明显卡顿数秒甚至失去响应。

其症结在于：双路递归生成了一棵巨大的二叉调用树。在树的每一层，节点数量以指数级翻倍展开。更为致命的是，左右子树之间存在大量完全相同的重叠子问题（Overlapping Subproblems）。

从图 3 可以清楚地看到，计算 fib(5) 时：

• fib(3) 被完全独立地计算了 2 次；
• fib(2) 被计算了 3 次；
• 基线节点 fib(1) 和 fib(0) 被反复触发了 8 次。

随着 n 的增大，整个调用树的节点总数逼近 O(2ⁿ)。当 n = 40 时，函数调用次数已突破 3 亿次，且绝大部分计算都是在重复进行相同的运算。

四、突破性能瓶颈：记忆化剪枝与迭代状态转移

面对多分支递归带来的指数级算力浪费，常规的工程优化手段有两种：记忆化自顶向下剪枝和迭代自底向上推进。

方法一：记忆化递归（Memoization）

既然子问题会被频繁重复调用，最直接的方法就是引入缓存容器（例如对象或 Map）。当某个 fib(k) 首次被计算出来后，先将其缓存到容器中；下次再次需要该值时直接查表返回，不再向下分支。

/**
 * 记忆化递归斐波那契数列 (时间复杂度 O(n), 空间复杂度 O(n))
 * @param {number} n
 * @param {Record<number, number>} memo
 * @returns {number}
 */
function fibonacciMemo(n, memo = {}) {
  if (!Number.isInteger(n) || n < 0) {
    throw new Error("输入参数必须为非负整数");
  }

  // 基线条件
  if (n === 0) return 0;
  if (n === 1) return 1;

  // 优先查缓存，若已计算直接返回结果
  if (memo[n] !== undefined) {
    return memo[n];
  }

  // 未缓存时进行单次计算，并存入 memo
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(50)); // 示例输出: 12586269025 (瞬间完成)

方法二：迭代状态转移（自底向上消除递归）

记忆化虽然将时间复杂度从 O(2ⁿ) 缩减到 O(n)，但仍然需要占用 O(n) 的调用栈深度与哈希表存储。实际上，计算 F(n) 时只需要前两个连续状态 F(n-1) 和 F(n-2)，完全可以通过一个极简的 for 循环实现自底向上的迭代计算，将空间复杂度进一步降至 O(1)。

/**
 * 迭代法斐波那契数列 (时间复杂度 O(n), 空间复杂度 O(1))
 * @param {number} n
 * @returns {number}
 */
function fibonacciIterative(n) {
  if (!Number.isInteger(n) || n < 0) {
    throw new Error("输入参数必须为非负整数");
  }
  if (n === 0) return 0;
  if (n === 1) return 1;

  let prev = 0; // 代表 F(n-2)
  let curr = 1; // 代表 F(n-1)

  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }

  return curr;
}

console.log(fibonacciIterative(50)); // 示例输出: 12586269025

五、调用栈安全守则：防范栈溢出与工程选型依据

在编写生产级别的 JavaScript 递归代码时，建议按照以下四个标准化步骤进行工程验证：

1. 递归编写的防御性检查清单

1. 首行放置基线判断：严禁在递归调用之后才处理基线边界，基线逻辑必须位于函数体最前沿。
2. 确保步长单向收敛：检查传入递归调用的参数，确保每次调用都在向基线数值移动（例如 n - 1），切勿出现步长为 0 或方向颠倒的情况。
3. 评估最大调用栈深度：若业务场景可能涉及成千上万层嵌套（如深度未知的超大树状结构数据），优先选择循环迭代，或手动借助数组模拟执行栈（显式栈），避免触发引擎硬性栈深度上限。