js实现fibonacci

JavaScript 实现斐波那契数列

斐波那契数列是一个经典的数学问题，其中每个数字是前两个数字的和，通常以 0 和 1 开始。以下是几种常见的实现方式。

递归实现

递归方法是最直观的实现方式，但效率较低，因为会重复计算相同的子问题。

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

迭代实现

迭代方法通过循环计算斐波那契数列，效率更高，适合大规模计算。

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 fibonacciDP(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibonacciDP(n - 1, memo) + fibonacciDP(n - 2, memo);
  return memo[n];
}

生成斐波那契数列

如果需要生成前 n 项的斐波那契数列，可以使用以下方法。

function generateFibonacciSequence(n) {
  const sequence = [0, 1];
  for (let i = 2; i < n; i++) {
    sequence.push(sequence[i - 1] + sequence[i - 2]);
  }
  return sequence.slice(0, n);
}

性能比较

• 递归方法的时间复杂度为 O(2^n)，适合小规模计算。
• 迭代和动态规划方法的时间复杂度为 O(n)，适合大规模计算。
• 动态规划方法在递归基础上优化，但需要额外空间存储中间结果。