S006-手写斐波那契数列

1.递归

function fibonacci(n) {
  if(n < 3){return 1};
  return fibonacci(n - 1) + fibonacci(n - 2)
}

2.循环

function fibonacci(n) {
  let num1 = 1;
  let num2 = 1;
  let sum = num2;
  for(let i = 1; i < n -1 ; i ++) {
    sum = num1 + num2;
    num1 = num2;
    num2 = sum;
  }
  return sum;
}

简化

function fibonacci(n) {
    let n1 = 1; n2 = 1;
    for (let i = 1; i < n - 1; i++) {
        [n1, n2] = [n2, n1 + n2]
    }
    return n2
}

3.尾递归

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

4.闭包

const fibonacci = function() {
  var mem = [0,1];
  var f = function(n) {
    var res = mem[n];
    if(typeof res !== 'number')  {
      mem[n] = f(n - 1) + f(n - 2)
      res = mem[n];
    }
    return res;
  }
  return f;
} ();

5.generator 函数和 for...of循环

function* fibonacci() {
  let [prev, curr] = [0, 1];
  // foo(,,) 相当于死循环，等于while(1)
  for(;;) {
    yield curr;
    [prev, curr] = [curr, prev + curr];
  }
}

for(let n of fibonacci()) {
  if(n > 1000) break;
  console.log(n)
}

6.箭头函数版本

let fibonacci = n => n > 1 ? fibonacci(n - 1) + fibonacci(n - 2) : n

7.Y Combinator + 箭头函数版本

// 100 就是传入的值
Y(f => n => n > 1?f(n - 1) + f(n - 2):n)(100)

上面递归写法虽然写法简单，但有性能问题

8.去除重复计算的递归版本

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

9.使用记忆函数优化正常递归版本

function memozi(fn) {
  let r = {}
    return function(n) {
      if(r[n] == null) {
        r[n] = fn(n)
        return r[n]
      } else {
        return r[n]
      }
    }
}

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