从斐波那契数列了解数学思维的短板（一）之重复计算

前提

斐波那契数列指的是这样的数列：1、1、2、3、5、8、13、21、34、··· ···
这个数列前两项都为1，从第三项起，每一项都等于前两项之和。

(由于在代码中一般第一项都为0，所以这里的第一项以0开始)



由于公式都已经被定义了，我们就直接写代码了！

转公式为代码

“看图写话”

const fib = (n) => 
            n === 0 ? 1 :
            n === 1 ? 1 :
           fib(n-1) + fib(n-2)

公式很好写，但是在运行的时候发现不对劲了，从fib(40)开始计算的越来越慢，fib(45)居然花了将近40秒！

不要慌张，小场面 —— 我们这是碰到了递归的坏处。

还记得我们在算法入门系列的第一篇文章提到的递归吗？不记得的话，请点击文章：《从最大值了解递归》。
在此处（斐波那契数列）我们也用到了递归（当然我们在第二篇文章《从汉罗塔问题了解数学思维的魅力》也用到了，用于每一篇的重点不同，就不要在意这些细节啦），我们可以简单画一下递归的过程：

递归带来的麻烦（一）

重复计算

我们以fib(6)来看递归的麻烦之处：

相同的彩色表示重复计算的次数，fib(2)、fib(1)、fib(0)被重新计算的概率太高了，而且只是n=6，总共就要25次递归运算，这会大大的降低性能。

特别说明：这里只是举例子说明数学思维 —— 递归带来的问题（一），下一章会继续写问题（二），下下章就是其他解决方法哟。

用人类思维来解决该问题

问题：出现了太多的重复计算。
思路：把计算过的数字放入数组，要用的时候直接取出来，从而减少重复计算次数。

1. 数字0，1默认为1，直接放入数组；
2. 将数字从2开始循环，由于规则是当前数字的值=前两项之和，所以从2开始给数组赋值；
3. 循环结束后返回最新的数组值。
   

   const fib2 = (n) => {
    const array = [1, 1];
   for(let i = 2; i <= n; i += 1) {
      array[i] = array[i-1] + array[i-2]
   }
   return array[n];
   }