js实现fibonacci

实现斐波那契数列的JavaScript方法

斐波那契数列是一个经典的数学问题，可以通过多种方式在JavaScript中实现。以下是几种常见的实现方法：

递归实现

递归是最直观的实现方式，但效率较低，尤其是对于较大的n值，因为会重复计算相同的子问题。

function fibonacciRecursive(n) {
  if (n <= 1) return n;
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

迭代实现

迭代方法通过循环来计算斐波那契数列，效率更高，适合处理较大的n值。

function fibonacciIterative(n) {
  if (n <= 1) return n;
  let a = 0, b = 1, temp;
  for (let i = 2; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

记忆化递归

记忆化技术可以优化递归实现，避免重复计算，提升性能。

function fibonacciMemoization(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
  return memo[n];
}

动态规划

动态规划方法通过存储中间结果来优化计算，适合处理较大的n值。

function fibonacciDP(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

生成器实现

使用生成器可以按需生成斐波那契数列，适合需要逐个获取数列项的场景。

function* fibonacciGenerator() {
  let a = 0, b = 1;
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

性能比较

• 递归：简单但效率低，时间复杂度为O(2^n)。
• 迭代：高效，时间复杂度为O(n)，空间复杂度为O(1)。
• 记忆化递归：优化了递归，时间复杂度为O(n)，空间复杂度为O(n)。
• 动态规划：高效，时间复杂度为O(n)，空间复杂度为O(n)。
• 生成器：适合按需生成数列，时间复杂度为O(n)（每次调用next()）。

根据具体需求选择合适的实现方式。对于大多数场景，迭代或动态规划是推荐的选择。