当前位置：首页 > JavaScript

js 递归实现

2026-03-14 22:34:35JavaScript

递归的基本概念

递归是一种函数调用自身的技术，通常用于解决可以被分解为相似子问题的问题。在JavaScript中，递归函数需要包含一个基线条件（终止条件）和递归条件（调用自身的条件）。

递归的示例：计算阶乘

阶乘是一个经典的递归示例。n的阶乘（n!）是所有小于或等于n的正整数的乘积。

function factorial(n) {
  if (n === 0 || n === 1) { // 基线条件
    return 1;
  } else {
    return n * factorial(n - 1); // 递归条件
  }
}
console.log(factorial(5)); // 输出: 120

递归的示例：斐波那契数列

斐波那契数列是另一个常见的递归示例，其中每个数字是前两个数字的和。

function fibonacci(n) {
  if (n <= 1) { // 基线条件
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2); // 递归条件
  }
}
console.log(fibonacci(6)); // 输出: 8

递归的注意事项

递归可能导致堆栈溢出，尤其是在处理大规模数据时。为了避免这种情况，可以使用尾递归优化或迭代方法替代。

尾递归优化

尾递归是一种特殊的递归形式，其中递归调用是函数的最后一步操作。某些JavaScript引擎（如ES6严格模式下的V8）支持尾递归优化。

function factorialTailRecursive(n, accumulator = 1) {
  if (n === 0) {
    return accumulator;
  } else {
    return factorialTailRecursive(n - 1, n * accumulator);
  }
}
console.log(factorialTailRecursive(5)); // 输出: 120

递归与迭代的选择

递归代码通常更简洁，但可能不如迭代高效。对于性能敏感的场景，迭代可能是更好的选择。

js 递归实现

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
console.log(factorialIterative(5)); // 输出: 120