js 斐波那契数列|极客笔记

js 斐波那契数列

在计算机科学中，斐波那契数列是一个非常经典的数学问题。斐波那契数列的定义如下：第0项为0，第1项为1，之后的每一项都是前两项的和。即F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n>=2)。

斐波那契数列的前几项为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

在这篇文章中，我们将讨论如何使用JavaScript来实现斐波那契数列的计算，并且探讨不同的实现方式。

递归实现

最直接的方式是使用递归来计算斐波那契数列。递归的思想就是将一个大问题拆分成更小的子问题来解决。下面是递归实现的代码：

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

// 输出斐波那契数列的前10项
for (let i = 0; i < 10; i++) {
    console.log(fibonacciRecursive(i));
}

以上代码中，fibonacciRecursive 函数接收一个参数 n，表示要计算第 n 个斐波那契数。如果 n 等于0或1，直接返回相应的值；否则递归地调用 fibonacciRecursive 来计算前两项的和。这种递归的实现方式简单直观，但是性能较差，因为会重复计算相同的值。

上面代码的输出为：

迭代实现

除了递归之外，我们也可以使用迭代的方式来计算斐波那契数列。迭代的思想是通过循环来逐步计算每一项的值。下面是迭代实现的代码：

function fibonacciIterative(n) {
    if (n === 0) {
        return 0;
    }

    let a = 0;
    let b = 1;
    let sum;

    for (let i = 2; i <= n; i++) {
        sum = a + b;
        a = b;
        b = sum;
    }

    return b;
}

// 输出斐波那契数列的前10项
for (let i = 0; i < 10; i++) {
    console.log(fibonacciIterative(i));
}

以上代码中，fibonacciIterative 函数也接收一个参数 n，表示要计算第 n 个斐波那契数。在循环中按照定义依次计算每一项的值，最终返回第 n 项的值。这种迭代的实现方式相对于递归来说更高效。

上面代码的输出为：

动态规划实现

动态规划是一种常用的解决问题的方法。在计算斐波那契数列时，也可以利用动态规划来优化计算过程。动态规划的思想是将原问题分解为若干个子问题，通过保存子问题的解来避免重复计算。下面是动态规划实现的代码：

function fibonacciDynamic(n) {
    let dp = new Array(n + 1).fill(0);
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// 输出斐波那契数列的前10项
for (let i = 0; i < 10; i++) {
    console.log(fibonacciDynamic(i));
}

以上代码中，fibonacciDynamic 函数创建了一个数组 dp 来保存计算过程中的中间值。在循环中依次计算第 i 项的值并保存在数组中，最终返回第 n 项的值。动态规划的实现方式能够避免重复计算，提高计算效率。

上面代码的输出为：