第四章 十万级斐波那契 (第1/1页)

    “依上题所述，若N在100000到400000之间，作何解？”

    杨成深吸一口气，他决定了，放弃递归，使用传统的线性方法，顺序遍历求解。

    这里的递归不是顺序的，斐波那契数列的递归方法是一种深度遍历求解，递归栈中函数作用域对象的开辟和回收都需要很多额外的性能开销，而顺序遍历不存在这样的情况。

    顺序遍历共享的是同一个作用域！

    可以使用两个临时的变量，因为公式f(n)=f(n-1) f(n-2)的缘故，要求第n项你只需要分别保存第n-1项和第n-2项的结果。

    这样做，将算法的空间复杂度降到了最低，和递归庞大的保存栈相比，优势就太大了。

    想清了思路，杨成正打算提笔就写，他突然想到一个令人震惊的后果。

    对于JavaScript，浮点数是有大小限制的，对于第几十万项的斐波那契数，它显然已经远远超出了浮点型的范围，那么，自己这个算法会不会导致溢出？

    好在他很快想通了，关卡设计者怎么会想不到这样的问题，自己只要能写出正确的算法来就OK了。

    这个算法其实并不难，杨成用了十几行代码就搞定了，他心里其实还是有些忐忑的，作为一名准程序员，有这种意识其实还是挺正常的。

    不是有个笑话吗，假如有人问一名程序员：你的程序是不是出Bug了？这个程序员听到后第一反应是：傻x你懂程序嘛？你会用嘛？而如果有人问程序员：这个效果和预期的有些不一致呢。那程序员肯定心想：糟了！肯定是出Bug了！