如何在JavaScript中计算斐波那契数列

斐波那契数列是以下模式中包含整数的数字序列。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..

从数学角度来看，计算斐波那契数列的一般公式是

fn = fn-1 + fn-2 ，其中n ≥ 2

在这里， **f 0 = 0 ** 和 **f 1 = 1 ** 。

我们需要计算给定整数 n 的 n 个斐波那契数，其中n≥0。

例子：

输入：n = 5
输出：[0, 1, 1, 2, 3]

输入：n = 10
输出：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

在本文中，我们将重点讨论两种主要且常见的计算斐波那契数列的方法。

使用 for循环 和 while循环
使用递归

使用循环： 使用这种方法计算斐波那契数列比递归方法更好。此方法使用 动态规划 ，它通过存储到目前为止生成的数字，然后在后续计算中使用它。

由于 n=1 和 n=2 的数字是固定的，即 0 和 1 ，所以可以通过以下逻辑计算系列中的其余数字：

f3 = f2 + f1
f4 = f3 + f2
f5 = f4 + f3
...
fn = fn-1 + fn-2

可以使用JavaScript中的 for循环 和 while循环 实现此逻辑。

使用for循环： 由于系列的前两个值是固定的，我们从i = 2开始循环，循环到i < n，因为数组索引从0开始，所以，n = 1在数组的情况下实际上意味着i = 0。

<script>
    const n = 10;

    // 创建长度为'n'的新数组
    var series = new Array(n);

    // 填充数组中的所有位置为0
    series.fill(0);   

    // 第一个元素的初始值
    series[0] = 0; 

    // 第二个元素的初始值
    series[1] = 1;  

    for(let i = 2; i < n; i++) {

        // 应用基本的斐波那契公式
        series[i] = series[i-1] + series[i-2];  
    }

    // 打印数列
    console.log(series);
</script>

输出：

如何在JavaScript中计算斐波那契数列

打印出了斐波那契数列的前10个元素

使用while循环：

<script>
    const n = 10;
      
    // 创建大小为'n'的新数组
    var series = new Array(n); 
      
    // 用0填充数组的所有位置
    series.fill(0);  
      
    // 第一个元素种子值
    series[0] = 0; 
      
    // 第二个元素种子值
    series[1] = 1;  
      
    // 初始化条件变量
    let i = 2;  
    while(i < n) {
  
        // 应用基本的斐波那契数列公式
        series[i] = series[i-1] + series[i-2];  
         
        // 递增条件变量
        i++;  
    }
      
    // 打印数列
    console.log(series); 
</script>

输出：

如何在JavaScript中计算斐波那契数列

打印出前10个斐波那契数列的元素

使用递归： 不推荐使用递归方法来打印整个斐波那契数列，因为递归算法本身在时间和复杂性方面是昂贵的，而且除了从特定位置获取斐波那契数列的值之外，我们还需要将它们存储在一个数组中，这会多次调用递归函数，即 n 次！

以下是在JavaScript中应用递归方法的示例。

<script>
    function fibonacci(n){
      if(n == 1) return 0;  // n=1时的返回值
      if(n == 2) return 1;  // n=2时的返回值
      
      // 递归调用
      return fibonacci(n-1) + fibonacci(n-2); 
    }
      
    const n = 10;
      
    // 创建大小为'n'的新数组
    var series = new Array(n); 
  
    // 用0填充数组的所有位置
    series.fill(0);   
      
    for(let i = 1; i <= n; i++) {
  
        // 存储第'i'个斐波那契数
        series[i-1] = fibonacci(i); 
    }
  
    // 打印数列
    console.log(series);
</script>