JavaScript递归函数实现阶乘与斐波那契数列运算

假设你在开发一个计算器或数据统计模块，遇到类似“求 5 的阶乘”或者“计算斐波那契数列第 10 项”的需求。直接写多层循环固然可行，但用递归往往能以最贴近数学定义的精炼逻辑解决问题。递归的核心思想就是“自身调用自身”，将一个庞大的问题逐层拆解为规模更小的同类子问题，直到触碰可以直接给出答案的最底层条件。

一、递归函数的底层双要素：基线条件与递推关系

任何一个能正确运行且不引起系统崩溃的递归函数，都必须具备两个不可分割的核心要素：

• 基线条件（Base Case）：也叫终止条件。当输入规模缩小到最简单的情况时直接返回确定的结果，从而截断无限自我调用的循环链路。
• 递推步骤（Recursive Step）：将当前问题分解为一个或多个更小规模的子问题，并包含对函数自身的调用。

二、使用递归实现阶乘（Factorial）运算

数学中正整数 n 的阶乘记为 n!，定义是所有小于及等于该数的正整数的乘积，并规定 0! = 1。用递推关系表达即为：

• 当 n = 0 或 n = 1 时，n! = 1（基线条件）
• 当 n > 1 时，n! = n × (n - 1)!（递推关系）

1. JavaScript 代码实现

function factorial(n) {
  // 参数合法性防御
  if (typeof n !== 'number' || n < 0 || !Number.isInteger(n)) {
    throw new TypeError('参数必须是非负整数');
  }
  
  // 基线条件（Base Case）
  if (n === 0 || n === 1) {
    return 1;
  }
  
  // 递推步骤（Recursive Step）
  return n * factorial(n - 1);
}

// 示例调用与输出
console.log(factorial(0)); // 示例输出: 1
console.log(factorial(4)); // 示例输出: 24
console.log(factorial(5)); // 示例输出: 120

2. 递归调用的“递进”与“回溯”过程

当执行 factorial(4) 时，JavaScript 引擎并非瞬间得出 24，而是经历两个阶段：

1. 递进（Pushing to Call Stack）：factorial(4) 等待 4 * factorial(3)，于是将当前上下文压栈；factorial(3) 继续调用并等待 3 * factorial(2)……直到调用 factorial(1)。
2. 回溯（Popping and Resolving）：factorial(1) 满足基线条件返回 1；上一层收到结果计算 2 * 1 = 2 并出栈；再上一层计算 3 * 2 = 6 出栈；最后顶层计算 4 * 6 = 24 完成整个求解。

三、使用递归实现斐波那契数列（Fibonacci）

斐波那契数列（Fibonacci sequence）是数学与计算机科学中的经典序列：0, 1, 1, 2, 3, 5, 8, 13, 21...。其数学规则规定前两项分别为 0 和 1，后续每一个数值都是其前两个数值之和：

• 当 n = 0 时，F(0) = 0
• 当 n = 1 时，F(1) = 1
• 当 n > 1 时，F(n) = F(n - 1) + F(n - 2)

1. 基础多路递归实现

function fibonacci(n) {
  if (typeof n !== 'number' || n < 0 || !Number.isInteger(n)) {
    throw new TypeError('参数必须是非负整数');
  }

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

  // 递推步骤（多路递归）
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 示例调用与输出
console.log(fibonacci(6)); // 示例输出: 8
console.log(fibonacci(10)); // 示例输出: 55

2. 朴素多路递归的性能缺陷与重叠子问题

与阶乘的“单链式”调用不同，斐波那契数列的递归调用会形成一棵二叉调用树。在求解 fibonacci(5) 时，程序会分别计算 fib(4) 与 fib(3)；而在展开 fib(4) 时，又会再次重复计算 fib(3)。随着 n 的增大，重复计算呈指数级膨胀，时间复杂度高达 O(2ⁿ)。

四、实际应用中的性能优化方案

1. 方案 A：记忆化缓存（Memoization）

为了解决斐波那契数列重复运算的问题，我们可以在计算过程中维护一个缓存对象。每次需要某个项时先查询缓存，如果已经计算过就直接读取，未计算过才执行递归并将计算结果存入缓存。这样可以将时间复杂度大幅降至 O(n)。

function fibonacciMemo(n, memo = {}) {
  if (n in memo) return memo[n]; // 命中缓存直接返回
  if (n === 0) return 0;
  if (n === 1) return 1;

  // 记录并返回
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(50)); // 示例输出: 12586269025 (极速计算)

2. 方案 B：尾递归优化（Tail Call Optimization）

如果函数在返回语句中仅仅调用自身，且不伴随乘法或加法运算（例如阶乘中的 n * factorial(n - 1) 伴随着乘法），当前栈帧在理论上就可以被复用，这就是尾递归。通过引入“累加器参数”，我们可以将阶乘改写为尾递归形式：

function factorialTail(n, accumulator = 1) {
  if (n === 0 || n === 1) {
    return accumulator;
  }
  // 尾调用：函数调用的返回值直接作为当前函数的返回值，无需额外计算
  return factorialTail(n - 1, n * accumulator);
}

console.log(factorialTail(5)); // 示例输出: 120

五、知识结构与选型对比总结

递归能够将数学上基于归纳法定义的问题直接转化为清晰易读的代码，但在计算工程实践中，必须综合考量调用栈开销和子问题特征：

掌握递归的关键在于先明确基线条件以防止死循环，再合理抽象递推关系，并在面对重复计算时主动引入记忆化缓存或迭代优化，从而在保持代码高可读性的同时兼顾执行效率。