JavaScript写斐波那契数列的几种方式

一时失言乱红尘 2022-05-27 12:52 125阅读 0赞

**什么是斐波那契数列：** 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>2，n∈N\*）（来源：[斐波那契数列——百度百科][Link 1]）  
**为什么要研究斐波那契数列：** 斐波那契数列为什么重要——知乎。  
知道概念后，如何用JavaScript函数斐波那契数列第N个数的值呢？

##### 1：递归（普通版） #####

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

这个方法算是代码最少也容易理解，但是当n较大时很快产生栈溢出，引发原因是“调用帧”过多，详情参阅[函数扩展之尾调用优化——阮一峰][Link 2]。

##### 2.递归（优化版） #####

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) { 
      if( n <= 1 ) {
       return ac2};
      return Fibonacci2 (n - 1, ac2, ac1 + ac2);
    }

此方式是函数尾调用优化之后的写法（默认参数ES6及以后版本支持，ES5请使用常规默认值写法），理解上稍微复杂，但是不会发生栈溢出，推荐使用。

##### 3.循环版 #####

function Fibonacci3(n){ 
        if (n===1 || n===2) { return 1; }
        let ac1 = 1, ac2 = 1;
        for (let i = 2; i < n; i++){ [ac1, ac2] = [ac2, ac1 + ac2]; }
        return ac2;
    }

循环版本最好理解，就是给初始值，然后不断的累加即可(用了解构赋值，代码更简洁)。

##### 4. generator版 #####

function* fibonacci() { 
         let [prev, curr] = [1, 1];
              while (true) {
                [prev, curr] = [curr, prev + curr];
                yield curr;
          }
    }
    function Fibonacci(n){ 
        if (n===1 || n===2) {
                return 1;
            }
        let ac = 0;
        const fibo = fibonacci();
        for (let i = 2;i < n; i++) {
          ac = fibo.next()
        }
        return ac.value;
    }

骚年，知道啥叫强行装逼最为致命不，这就是乱用新东西的典范（其实嘛，也可以当做顺便学学），不过generator用来生成斐波那契数列还是不错的，for of迭代妥妥的。

[Link 1]: https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
[Link 2]: http://es6.ruanyifeng.com/#docs/function