当前位置：首页 > JavaScript

js 递归怎么实现

2026-04-07 17:02:22JavaScript

递归的基本概念

递归是一种通过函数调用自身来解决问题的方法。在 JavaScript 中，递归通常用于处理具有重复结构的问题，例如树形遍历、阶乘计算等。

递归的实现步骤

定义一个递归函数需要明确两个部分：基线条件（递归终止条件）和递归条件（调用自身的条件）。基线条件用于防止无限递归，递归条件用于分解问题。

示例：计算阶乘

阶乘是一个经典的递归问题。n 的阶乘（n!）定义为 n (n-1) (n-1) ... 1。

js 递归怎么实现

function factorial(n) {
  // 基线条件：0 或 1 的阶乘是 1
  if (n === 0 || n === 1) {
    return 1;
  }
  // 递归条件：n! = n * (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 输出 120

示例：斐波那契数列

斐波那契数列的第 n 项是前两项的和，其中第 0 项为 0，第 1 项为 1。

function fibonacci(n) {
  // 基线条件
  if (n === 0) return 0;
  if (n === 1) return 1;
  // 递归条件：fib(n) = fib(n-1) + fib(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

递归的注意事项

栈溢出问题：递归会占用调用栈空间，如果递归深度过大（如未正确设置基线条件），会导致栈溢出错误。
性能优化：某些递归问题（如斐波那契数列）存在重复计算，可以通过记忆化（Memoization）优化性能。

优化递归：记忆化

记忆化是一种缓存中间结果的技术，避免重复计算。

js 递归怎么实现

function fibonacciMemo(n, cache = {}) {
  if (n in cache) return cache[n];
  if (n === 0) return 0;
  if (n === 1) return 1;
  cache[n] = fibonacciMemo(n - 1, cache) + fibonacciMemo(n - 2, cache);
  return cache[n];
}

console.log(fibonacciMemo(50)); // 快速输出结果

尾递归优化

某些语言支持尾递归优化（TCO），但 JavaScript 引擎的实现并不一致。尾递归可以避免栈溢出，但需确保递归调用是函数的最后一步操作。

function factorialTailRecursive(n, accumulator = 1) {
  if (n === 0) return accumulator;
  return factorialTailRecursive(n - 1, n * accumulator);
}

console.log(factorialTailRecursive(5)); // 输出 120

递归与循环的对比

递归代码通常更简洁，但可能不如循环高效。对于性能敏感的场景，可以考虑用循环替代递归。

function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorialLoop(5)); // 输出 120