JavaScript|斐波纳契数列

斐波纳契数列定义：

斐波那契数列（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*）

递归实现：

function fib(n) { 
    return n < 2 ? n : (fib(n - 1) + fib(n - 2)); 
}

<i>递归实现的难点在于对递归函数的理解</i>

非递归借助数组实现：

function fib(fibonacci) {
    return fibonacci[fibonacci.length - 1] + fibonacci[fibonacci.length - 2];
}

function main() {
    const n = document.getElementById("n").value;
    let fibonacci = [1, 1];
    for (let i = 0; i < n - 2; i++) {
        fibonacci.push(fib(fibonacci));
    }
    alert(fibonacci[fibonacci.length - 1]);
}

<i>n值较大时，数组会占用一定的内存空间</i>

非递归直接使用加法：

function fib(n) { 
  if (n < 2) { 
    return 1; 
  }  
  let a = 1, b = 1; 
  for (let i = 2; i < n - 1 ;i++ ) { 
    b = a + b; 
    a = b - a; 
  } 
  return a + b; 
}

<i>当n足够大时，建议使用直接加法</i>

如有错误，请指正，谢谢 ~