目錄
1.前情提要
1.1題目:搭電梯
1.2輸入輸出範例
2.開始解題
2.1什麼是費式數列
2.2遞迴表示
2.3遞迴的複雜度(2^n)
2.4快取暫存的作法
2.5尾遞迴(tail recursive)的作法
2.6疊代(iterative)的作法-空間換取時間
3.全部的Code
4.小心得
前情提要
由於在刷題的時候遇到了一個題目，恍然大悟他原來在考費式數列啊!因此來多了解一些費式數列。
題目:搭電梯
有一台電梯部分故障，他每次只能往上一層樓或是往上兩層樓，其餘樓層不能直達，如果從一樓要去五樓，進入電梯有兩個選擇，分別是按二樓或三樓，假設按了三樓，那接下來只能按四樓或五樓，以此類推，依照電梯特殊運行的方式，要來計算到某一個樓層共有幾種方法。
輸入輸出範例
所以如果要到五樓，共有五種方法可以抵達。
看完題目不熟的時候，有點難聯想要用費氏數列來解，那先來看看~
開始解題
什麼是費式數列
我們常可以看到他的另外一個稱呼是:Fibonacci 斐波那契數列，他是一種數列，可以用遞迴的方式來表示:
- 第0個數為0
- 第1個數為1
- 接下來的數為前兩數之和
也就是從頭開始為:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…。
遞迴表示
這就屬於以遞迴的方式表達，那對我而言也是最淺顯易懂，最直譯的方式。
遞迴的複雜度(2^n)
常見的有六種時間複雜度的分類，其中一類為O(2^n)，這也是費氏數列所在的類，可參考: 初學者學演算法｜從費氏數列認識何謂遞迴
有關於於當執行到第N層時，為什麼複雜度會變成2的N次方，可以參考以下影片 : 什麼是費氏數列 in python -part 1- recursive
這一個類別O(2^n)，表示，執行步驟會是2的n次方，簡單想因為它都需要呼叫到最底層fibo(1)和fibo(0)，可以想像當輸入數字持續增大時，所花費的時間不是線性增長，而是倍數增加了!
當我們要輸入一個很大的數，程式則終止無法運算了，為了要解決這個問題我們需要用空間換取時間。
快取暫存的作法
因為每一回合，都需要前兩個數相加，所以如果把每一個數列的數都存下來，接下來就不用遞迴到最底層0或是1的時候了!
可以參考 :什麼是費氏數列 in python -part 2- lru_cache
使用快取的方式，用functools package 存下每一個數值，讓他變成一個數列，這時候運算過的數值例如，n=3、n=4、n=5都會被依序存下來。
那來簡介一下 functools package 的 lru_cache，它是一個可以提供函數緩存(快取、暫存)功能的裝飾器，在費氏數列中使用它，就是為了把每次計算值都暫存下來，好讓後續繼續使用這些數值，而不用再次運算。
可以參考: Python｜functools｜lru_cache fibonacci numbers ( 費氏數列 )
尾遞迴(tail recursive)的作法
可參考: 什麼是費氏數列 in python -part 3- tail recursive
遞迴會面臨到一個問題是，會一直call已經計算過的，可以用尾遞迴解決這個問題，使用到的重要觀念是把當前的計算結果，傳到下一層去，這樣做和原本的遞迴的作法是不同，原本遞迴則是一直重複計算直到最底層，那尾遞迴可以想像成反過來，它把算好的丟到下一層去，就不用重複計算了!
疊代(iterative)的作法-空間換取時間
上面的幾個方法，其時間複雜度還是停留在2的N次方，那要把時間複雜度降低，降成N可以採用這樣的方式。
參考: 什麼是費氏數列 in python -part 4- iterative
這個方法真的最美，最乾淨的code，而且效率和可以的範圍也是最好的。
全部的Code
小心得
回到這一個搭電梯的題目，如果牽扯到1或2，往上一層往上兩層這樣的關鍵字時，就可以去和遞迴做聯想，另外遞迴的方法有這幾種，統整下來:
- 一般的遞迴
- 使用快取暫存( functools package 的 lru_cache)
- 尾遞迴
- 疊代
通過練習，更完整的認識遞迴，下次遇到遞迴問題時，可以把它寫得更美了!
❤️感恩看到這裡的你，希望這篇文章有幫上你👏歡迎拍手給我鼓勵，我是甜不辣馬拉松，我們下次見
