> 问渠那得清如许，为有源头活水来。 想要保持自己的技术活力，最有效的手段就是通过不断地输入来提供足够的养分。我们也不必刻意追求高深的或者新鲜的知识点，通过对一个基础问题的全方位多维度解析，同样也会收获不小。  ## 题目 有这么一道题目需要我们来解答： - 试输出斐波那契数列的前10项，即 1、1、2、3、5、8、13、21、34、55。 ## 分析 有些人看到题目中出现了“斐波那契数列”这个概念后，可能脑袋就蒙圈了，其实大可不必！ 对于这道题，可以不用理会这个陌生概念，我们只需要关心后面它给出的数字规律即可。 我们可以看到，规律总结起来就一句话：**从第三位开始，后面每项的值等于前两项之和**，用式子表示的话就是：a~n~ = a~n-1~ + a~n-2~（n ≥ 2） 。 根据题目要求，其实就是要我们做两件事： 1. 生成每一项的值。 2. 打印输出所有值。 ## 基础解法 **解题思路：** - 创建一个数组存放数列各项的值。 - for 循环生成数列各项并存入数组（为了计算后面各项的值），打印生成的项。 **代码实现如下：** ```javascript /** * @description 创建一个生成数列数组的方法 * @param {number} n 表示要生成多少项（即数组长度，不是数组下标） */ function createFibArr(n) { // 声明一个存放数据的数组 let fibArr = []; // 从第三项(下标为2)开始，每一项都等于前两项之和 for (let index = 0; index < n; index++) { index < 2 ? fibArr.push(1) : fibArr.push(fibArr[index - 1] + fibArr[index - 2]); console.log(fibArr[index]); } } // 调用方法 createFibArr(10); ``` **分析：** 这应该是最基本的解题方法，很容易就实现了。 但如果这是面试题的话，这样的答案只能说是中规中矩，没有出彩的地方，最重要的是体现不出我们与众不同的气质啊，所以，我们应该用点其他的手段来提升下自己的逼格！ ## 初级递归 **解题思路：** - 通过递归的手段计算出各位置对应的值（这里有个前提是：第一项和第二项是确定值，否则，递归就不好用了）。 - 打印结果。 **代码实现如下：** ```javascript /** * @description 计算出第 n 项的值 * @param {number} n 表示每一项的下标值 * @returns {number} 下标为 n 的位置的值 */ function calFibValue(n) { console.count("执行次数：") return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2)); } /** * @description 打印计算结果 * @param {number} n 代表要打印多少项 */ function printRes(n) { for (let index = 0; index < n; index++) { console.log(calFibValue(index)); } } // 调用打印方法 printRes(10); // 执行次数：: 276 ``` **分析：** 递归的使用确实提升了代码的逼格，但是又引来了另外一个问题：性能问题。 每一项的值都是从第一项开始计算累加 出来的，比如计算第四项的值，其过程如下： 1. 返回第一项的值：1 。 2. 返回第二项的值： 1 。 3. 计算第三项的值为 1 + 1 = 2 。 4. 计算第四项的值为 2 + 1 = 3 。 在计算第五项值的时候，还要经过上面这个过程来获取第四项的值，进行了大量的重复运算。 为了惊艳面试官，我们还需要再做优化！ ## 递归优化 **解题思路：** - 导致重复计算的是递归那部分的逻辑，所以优化点在递归这里。 - 既然存在重复运算，那就意味着其实后面的运算完全可以使用前面已经计算出来的值，所以我们需要引入缓存来保存每次的计算结果。 **代码实现：** ```JavaScript /** * @description 计算出第 n 项的值 * @param {number} n 表示每一项的下标值 * @returns {number} 下标为 n 的位置的值 */ // 存放每次计算结果的 Map 结构 // 这里也可以用数组，但是在语义方面没有 Map 或对象直接 let fibValueMap = new Map(); function calFibValue(n) { console.count("执行次数："); // 如果缓存中已存在对应的值，则直接返回 if (fibValueMap.has(n)) { return fibValueMap.get(n); } const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2)); // 在计算出每一项的之后，需要及时存入 Map fibValueMap.set(n, value); return value; } /** * @description 打印计算结果 * @param {number} n 代表要打印多少项 */ function printRes(n) { for (let index = 0; index < n; index++) { console.log(calFibValue(index)); } } // 调用打印方法 printRes(10); // 执行次数：: 26 ``` **分析：** 根据打印出来的 count 来看，优化后的递归次数是优化前的 1/10 左右，这个结果就很惊喜了。 这次面试官应该可以满意了吧。 ## 总结 万变不离其宗，只要将解题思路理清了，代码实现只是一个结果而已。在平常的工作学习中，我们要有意识地培养自己的发散性思维，从多角度去看待问题，你可能会发现不一样的风景哦！希望能够对大家有所启发哦！ 在面试中，为了突显自己的独特气质或者人家面试题目就有具体要求的，我们使用一些看起来高大上的思路，这无可厚非。 但是呢，在平常的工作中，我还是更建议大家：在性能相近的情况下，能使用基础方法解决的一般不要用“高档”方法，因为基础方法出错的概率小很多。就比如今天这道题，其实基础解法的性能是最好的。 少写 BUG，我们才能有更多的时间来摸鱼，不是吗？ ~ ~ 本文完，感谢阅读！ ~ > 学习有趣的知识，结识有趣的朋友，塑造有趣的灵魂！ > > 我是〖编程三昧〗的作者 **隐逸王**，我的公众号是『编程三昧』，欢迎关注，希望大家多多指教！ > > 你来，怀揣期望，我有墨香相迎！ 你归，无论得失，唯以余韵相赠！ > > 知识与技能并重，内力和外功兼修，理论和实践两手都要抓、两手都要硬！