一個小小工程師的心情抒發天地

        
    今天要來寫教學，一樣是面試題目很常考的東西，就是寫到爛的Fib        
(不知道為什麼公司都很喜歡考這個，和Linked list=_= | ) 。

    費波那西數列(Fibonacci)，大陸叫"斐波那契数列"，在本文，我們統一用Fib就好。

故事 :     

根據高德納（Donald Ervin Knuth）的《計算機程式設計藝術》（The Art of Computer Programming），1150年印度數學家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（義大利人斐波那契Leonardo Fibonacci），他描述兔子生長的數目時用上了這數列:
第一個月初有一對剛誕生的兔子
第二個月之後（第三個月初）牠們可以生育
每月每對可生育的兔子會誕生下一對新兔子
兔子永不死去

假設在n月有兔子總共a對，n+1月總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，前一月（n+1月）的b對兔子可以存留至第n+2月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在n月就已存在的a對

定義 :    F[0] = 0
        F[1] = 1 
        F[n] = F[n-1]+F[n-1] (n>=2)
        用文字來說，就是費波那契數列由0和1開始，之後的費波那契系數就是由之前的兩數相加而得出。首幾個費波那契系數是：
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……（OEIS中的數列A000045）

特別指出：0不是第一項，而是第零項。

 看完了這些，估計大家都想睡了吧，來吧 ! 我們直接進到程式裡面，這樣也比較好了解。
 

 首先，我們先來看"遞迴版本" ( 大部份的公司還是會比較喜歡用這種方式來考  )
                                                          

和最近似乎流行起來的 非遞迴版本

不知道從什麼時候開始這種題目也開始流行起來，其實算一次之後，真的不會很難的，本魯已經盡量減輕大家負擔了，請大家動手試試看吧。