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()）。
根据具体需求选择合适的实现方式。对于大多数场景，迭代或动态规划是推荐的选择。
