当前位置：首页 > JavaScript

js实现fibonacci

2026-04-06 01:56:19JavaScript

Fibonacci数列简介

Fibonacci数列是一个经典的数学序列，其定义如下：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)（n ≥ 2）。在JavaScript中可以通过多种方式实现Fibonacci数列的计算。

递归实现

递归是最直观的实现方式，但性能较差，时间复杂度为O(2^n)，不适合计算较大的n值。

function fibonacciRecursive(n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
console.log(fibonacciRecursive(10)); // 输出55

迭代实现

迭代方式通过循环计算Fibonacci数列，时间复杂度为O(n)，性能优于递归。

function fibonacciIterative(n) {
    let a = 0, b = 1, temp;
    for (let i = 0; i < n; i++) {
        temp = a;
        a = b;
        b = temp + b;
    }
    return a;
}
console.log(fibonacciIterative(10)); // 输出55

动态规划实现

动态规划通过存储中间结果避免重复计算，时间复杂度为O(n)，空间复杂度也为O(n)。

js实现fibonacci

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];
}
console.log(fibonacciDP(10)); // 输出55

优化的动态规划实现

通过仅保存前两个值，可以将空间复杂度优化为O(1)。

function fibonacciOptimized(n) {
    if (n <= 1) return n;
    let prev = 0, curr = 1;
    for (let i = 2; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}
console.log(fibonacciOptimized(10)); // 输出55

闭包实现

利用闭包可以缓存计算结果，避免重复计算，适合多次调用的情况。

const fibonacciClosure = (function() {
    const cache = [0, 1];
    return function(n) {
        if (cache[n] !== undefined) return cache[n];
        cache[n] = fibonacciClosure(n - 1) + fibonacciClosure(n - 2);
        return cache[n];
    };
})();
console.log(fibonacciClosure(10)); // 输出55

矩阵快速幂实现

矩阵快速幂是一种高效的算法，时间复杂度为O(log n)，适合计算非常大的n值。

js实现fibonacci

function multiply(a, b) {
    return [
        [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
        [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
    ];
}

function matrixPower(mat, power) {
    let result = [[1, 0], [0, 1]];
    while (power > 0) {
        if (power % 2 === 1) {
            result = multiply(result, mat);
        }
        mat = multiply(mat, mat);
        power = Math.floor(power / 2);
    }
    return result;
}

function fibonacciMatrix(n) {
    if (n <= 1) return n;
    const mat = [[1, 1], [1, 0]];
    const result = matrixPower(mat, n - 1);
    return result[0][0];
}
console.log(fibonacciMatrix(10)); // 输出55

生成器实现

使用生成器可以按需生成Fibonacci数列，适合需要逐个获取的场景。

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

const gen = fibonacciGenerator();
for (let i = 0; i <= 10; i++) {
    console.log(gen.next().value); // 输出0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
}

尾递归优化实现

某些JavaScript引擎支持尾递归优化，可以减少递归调用的堆栈开销。

function fibonacciTailRecursive(n, a = 0, b = 1) {
    if (n === 0) return a;
    if (n === 1) return b;
    return fibonacciTailRecursive(n - 1, b, a + b);
}
console.log(fibonacciTailRecursive(10)); // 输出55