灯的个人博客

forever young,forever weeping.

0%

斐波那契额数列第n位

发表于 更新于 分类于

斐波那契额数列第n位 算法题

个人题解

递归的方式

1
2
3
4
5
6
7
function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(40)

结论:

  • 运行时间为1360ms左右,性能比较差
  • 到45位的时候计算时间已经是15s

递归的方式,加一层缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fibonacci(n, cache) {
  if (n === 0 || n === 1) {
    return n;
  }
  if (!cache) {
    cache = {};
  }
  if (cache[n]) {
    return cache[n];
  }
  cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
  return cache[n];
}
fibonacci(40)

结论:

  • 第5000位的时候是9ms,此时数值已经是超过js最大数值,为Infinity
  • 9000位左右递归栈会爆掉

循环的方式

1
2
3
4
5
6
7
8
function fibonacci(n) {
  let arr = [0, 1];
  for (let i = 0; i < n; i++) {
    arr.push(arr[arr.length - 1] + arr[arr.length - 2]);
  }
  return arr[n - 1];
}
fibonacci(50)

结论:

  • 性能最佳,5000位约7毫秒

总结

  • 递归一般情况下性能比普通循环要低
  • 递归可能会爆栈
  • 除非必须要递归的方式、其他方案成本过高、能确定递归次数较少,不然不建议用递归
  • 某些文档提到尾递归可以提高性能,但是这个斐波那契额数列,没有找到使用尾递归的方式,单独开一篇尾递归的内容