斐波那契数列

一直以来很恐惧递归，就算使用也是懵懵懂懂，今天想到了斐波那契数列，顺便学习下递归

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

1. 基础版

function fibonacci(n) {
    if(n <= 0) {
        return 0
    }else if(n === 1) {
        return 1
    }else {
        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}

该方法代码优美逻辑清晰，但是存在大量的重复计算。实际操作其实是将每个元素层级变成最低的数字1进行相加，所以运算量大。

2. 循环版本

function fibonacci(n) {
    if(n <= 1) {
        return n
    }
    let a = 0
    let b = 1
    for(let i = 2; i <= n; i ++) {
        [a, b] = [b, a + b]
    }
    return b
}

该方法代码逻辑清晰，且不存在大量的重复计算。实际操作其实是将变量变成数列位置前两位进行进行相加操作。

3. 递归改良版

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

4. 记忆函数优化

function memozi(fn){
  var r = {}
  return function(n){
    if(r[n] == null){
      r[n] = fn(n)
      return r[n]
    }else{
      return r[n]
    }
  }
}
var fibfn = memozi(function(n){
    if(n==0){
        return 0
    }else if(n==1){
        return 1
    }else{
        return fibfn(n-1) + fibfn(n-2)
    }
})