引出问题
递归中经典的题目就是斐波那契数列，而且在面试中，面试官也特别喜欢问你这道题。
如果换做是你，面试官让你写一个递归函数获取斐波那契数列第n个数的值，想必你的做法是这样的：
function fibonacci1(n) { if(n == 1 || n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2)}
先声明一点，这样的写法是完全正确的，同时这也能体现出递归的优点，那就是代码简洁，但与此同时缺点也非常的明显，那就是效率非常低，不信我们来看个例子
Q：请求出斐波那契数列中第6个数的值
我们来分析一下解决该问题时的过程，如下图所示
很明显得看到，递归过程中，有很多值重复求了不止一次，例如 4 和 3 ，若我们要获取得数比6还大的话，重复求值的现象会更加的明显，这无疑是很消耗性能的
接下来就介绍另一种方式，来提高这个方法的效率
解决办法
递归的过程会造成重复求值的现象是因为我们是从第n个数开始往前推导的，而只有第1个数和第2个数是已知的，值为1，所以其它所有的值都要根据它俩来求得。
所以我们想到的办法就是不妨从前往后推，首先我们可以创建个数组，从第一个数开始，在该数组中记录每个索引位置上的值，代码如下：
function fibonacci2(n) { // 记录斐波那契数列 第1个数 到 第n个数 的所有值 let arr = [1, 1] // 获取n个数之前所有的值，并存储在arr中 for(let i = 2; i < n; i++) { arr[i] = arr[i - 1] + arr[i - 2] } // 直接从arr中返回我们要的值 return arr[n - 1]}
换个角度来说，我们在求解过程中，将所有求过的值都记录存储了下来，因此不用像递归一样重复求值，所以这是一种非常高效的做法
效率比较
我们来比较一下上面两种求取斐波那契数列方法的效率
// 递归求取的开始时间let start1 = Date.now()// 递归求取第40个数的值console.log(fibonacci1(40))// 递归求取的结束时间let end1 = Date.now() // 高效的方法求值的开始时间let start2 = Date.now()// 高效的方法求取第40个数的值console.log(fibonacci2(40));// 高效的方法求值的结束时间let end2 = Date.now() console.log(`递归所用时间：${end1 - start1} ms高效的方法所用时间：${end2 - start2} ms`);/*102334155102334155 递归所用时间：2476 ms高效的方法所用时间：0 ms*/
从结果我们能很明显地看到，仅仅第40个值对于高效的方法来说根本不算什么，使用的时间几乎为0，而递归却因重复求值使用了2s以上的时间。因此可以想象，如果我们要获取斐波那契数列第1000个甚至第100000个的值，那递归求值得花多少时间啊？
