509.斐波那契数

[shengxinjing]

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。

 

示例 1：

输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1. 示例 2：

输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2. 示例 3：

输入：4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

https://leetcode-cn.com/problems/fibonacci-number/

[aniu2016]

var fib = function(N) {
  if(N === 0 || N=== 1) return N;
  let preNum = 0,currNum = 1,index = 1,result;
  while (index !== N) {
    result = preNum + currNum;
    preNum = currNum;
    currNum = result;
    index ++;
  } 
  return currNum;
};

[kaizige10]

标题可以加一下题号：509

我的思路是缓存：

// 缓存
const cache = new Map()
var fib2 = function (N) {
    if (N === 0) return 0
    if (N === 1) return 1
    if (cache.has(N)) return cache.get(N)
    const result = fib(N - 2) + fib(N - 1)
    cache.set(N, result)
    return result
};

用时最短是56ms

[shengxinjing]

@kaizige10 cool 带优化版的递归

[kouchao]

const c = {}
var fib = function(N) {
    if(N <= 1) {
        return N
    }
    if(c[N]){
        return c[N]
    }
    c[N] = fib(N - 1) + fib(N - 2)
    
    return c[N]
};

执行用时 :56 ms, 在所有 JavaScript 提交中击败了95.60%的用户 内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了84.36%的用户

[TimCN]

var fib = function (N) {
  if (N < 2) {
    return N;
  }

  let fibN = 1;
  let preFibN = 0;
  let temp;

  for (let i = 2; i <= N; i++) {
    temp = fibN;
    fibN = fibN + preFibN;
    preFibN = temp;
  }
  return fibN;
};

1. 开始怀疑，什么时候使用递归，什么时候使用循环；是否循环优于递归，特别是在有函数作用域的语言中，函数也是一个开销； @shengxinjing ,求解答