我们知道斐波那契数列 (也称作兔子数列) 1,1,2,3,5,8,13,21,34.....
前两位数固定是 1, 之后每一位数都是前两位数的之和, 这样的数列就是斐波那契数列
那么我们要求这样的数列, 就必须要求 n-1 和 n-2 位数
- function getFB(n){
- if(n == 1 || n == 2){
- // 这里我们先保持前两位数是 1
- return 1;
- }else {
- return getFB(n-1) + getFB(n-2);
- }
- }
- console.log(getFB(10));
求斐波那契数列的第十位 在控制台中打印出来的是 55
那么 第五十位呢?.........
很好, 我的浏览器卡死崩溃了
由此我们可知, 这样求斐波那契数列实在是太浪费性能了
既然有问题我们就来解决它
那么 求斐波那契数列的时候是为什么会浪费性能呢?
原因就是浏览器求了太多重复项
- var i = 0; // 声明一个变量, 用来记录调用 getFB() 方法的次数
- function getFB(n){
- i++;
- if(n == 1 || n == 2){
- return 1;
- }else {
- return getFB(n-1) + getFB(n-2);
- }
- }
- console.log(getFB(20));// 我的浏览器求不出来这么多项 所以换了小一点的数字
- console.log(i);
求斐波那契数列的第 20 位会调用 13529 次函数
那么求第 30 位呢?
多达 16 万次
第 40 位呢? 第 50 位呢?.......
所以这个样子实在是太浪费性能了
解决问题的思路: 我们把已经求过的项用一个变量保存起来, 如果下次还需要用到这个项就直接取出来用, 而不是再去调用函数
- var i = 0;// 声明一个变量 i, 记录调用 getFB 这个函数的次数.
- // 声明一个对象 obj, 用来保存已经求过的项.
- var obj = {};
- function getFB(n){
- i++;
- // 求 n 位是多少, 就先去 obj 里面看看, 之前求过没有, 如果之前求过, 就直接取出来使用.
- if(obj[n] != undefined){
- // 如果进到了这里, 说明当前这个 n 位已经求过, 已经存进 obj 里面了
- return obj[n];
- }else {
- // 如果进到这里来了, 就说明当前这个 n 位之前没求过, 没求过就求呗.
- if(n == 1 || n == 2){
- obj[n] = 1;
- return 1;
- }else {
- obj[n] = getFB(n-1) + getFB(n-2);
- return obj[n];
- }
- }
- }
- console.log(getFB(60));
- console.log(i);
那么我们就来看看结果吧
斐波那契数列的第 60 位大的吓人, 但是我们却也只调用了 117 次函数, 极大的提高了性能
来源: https://www.cnblogs.com/mlw1814011067/p/9439651.html