概要：

斐波那契数列(Fibonacci sequence),又称黄金分割数列 [1],因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称“兔子数列”,其数值为:1、1、2、3、5、8、13、21、34……在数学上,这一数列以如下递推的方法定z义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)

实现方式：

1.普通递归：

function fib1(n) {
    if(n === 0 || n === 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

使用F(n)=F(n - 1)+F(n - 2)这个公式配合递归完成，时间复杂度是0(2^n),空间复杂度是0(n),相对来说是性能比较差的一种方式。

2.尾递归：

function fib2(n,a = 0,b = 1) {
    if(n === 0) return a;
    if(n === 1 ) return b;
    return fib2(n - 1, b,a+ b)
}

 这种方式从n开始由大到小线性累加结果，将本次计算结果直接传入下一次递归的参数位置，这样即降低了时间复杂度，又降低了空间复杂度，性能相对于第一种方式大大提升。时间复杂度为0(n)，空间复杂度为O(1)。

3.动态规划：

function fib3(n) {
    if( n === 0 || n === 1) return n
    let a = 0,b = 1;
    let temp = 0;
    for(let i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp
    }
    return temp;
}

这种方使用遍历方式，在每次遍历时通过变量不断累加结果值，减少了时间复杂度，但相较于第二种来说其由于使用了多余的变量，空间复杂度更高。时间复杂度为O(n)，空间复杂度为O(1).

4.Binet方程:

function fib4(n) {
    if( n === 0 || n === 1) return n;
    const sqprt5 = Math.sqrt(5); 
    const phi = (1 + sqprt5) / 2; // 求出黄金分割比
    return Math.round((Math.pow(phi,n)  - Math.pow(1 - phi,n)) / sqprt5);
}

Binet方程是一个用于计算斐波那契数列中任意一个数的公式,形式如下: F(n) = (φ^n - (1-φ)^n) / √5 其中φ是黄金分割比例,它的值约为1.6180339887,√5表示根号5。这种方式用到已有的计算公式，时间复杂度与空间复杂度均是O(1)，算是求斐波那契数列性能最好的一种方式。