初學者學演算法｜從費氏數列認識何謂遞迴

程式麻瓜的程式知識課（七）

Source: https://burst.shopify.com/photos/laptops-at-workstations-coding

在初學者學演算法系列的第一篇文章中，我們認識了演算法這個玩意兒，也對評斷演算法好壞的工具「時間複雜度」有了基本的概念。在前兩篇文章中，我們分別介紹了三個演算法入門的必備知識：選擇排序法、插入排序法與合併排序法。

而在合併排序法的程式碼實作中，我們偷偷運用到了一點遞迴的觀念，接下來，就讓我們一邊認識 O(2^n) 的費氏數列算法以及遞迴觀念。

目錄：常見的六種時間複雜度與演算法

1. O(1)：陣列讀取
2. O(n)：簡易搜尋
3. O(log n)：二分搜尋
4. O(n²)：選擇排序法、插入排序法
5. O(n logn)：合併排序
6. O(2^n)：費波那契數列

O(2^n)：費波那契數列 (Fibonacci numbers)

時間複雜度為 O(2^n) 的演算法，代表著執行步驟會是 2 的 n 次方。實務上來說，這樣的執行效率非常的慢，例如當輸入為 100 時，執行步驟就會暴增到 30 位數，等於即使每秒都能執行 1 百億個步驟，也需要個天荒地老 1 千億年才能完成。因此，這樣的時間複雜度是大部分工程師在設計演算法時想要避免的。

而這樣的時間複雜度，最常見的例子是以遞迴計算費波那契數列 (Fibonacci numbers)。

費波那契數列

所謂費波那契數列，是指在一串數字中，每一項是前兩項的和。數學上的定義為：

• 第 0 項 = 0
• 第 1 項 = 1
• 第 n 項 = 第 n-1 項 + 第 n-2 項

從上面的數學定義，我們可以簡單列出數列的 0 到 10 項為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55。

知道了何謂費波那契數列後，接著我們就要先來解釋如何計算在程式中計算數列的第 n 項為何，以及為何它的時間複雜度為 2 的 n 次方。

計算費波那契數列第 10 項的程式碼如下：

def fibo(n):
    if n == 0:
        return 0;
    elif n == 1:
        return 1;
    return fibo(n-1) + fibo(n-2)
​
print(fibo(10))

觀察上面的程式碼我們可以看到，程式碼的設計幾乎只是單純地把數學定義寫成程式碼。接下來，我們就要藉由上面的這段簡單程式碼，解答讀者心中可能長久以來未解的迷惑：何謂「遞迴」？

從費波那契認識遞迴

所謂遞迴，最簡單的定義就是

在函式之中呼叫函式自己本身

所謂函式，我們可以簡單理解成它是一個把一串程式碼包成一個動作的工具。而執行這一個動作就稱為呼叫。

以 Python 為例，我們會用 def 把下面所有縮排的那串程式碼包成一個動作。def 後面是這個動作的名稱，名稱後面的括弧裡放著這個動作所要使用的參數。return 則是將這個動作賦予一個值，把 return 後面接的東西賦予給它。

以 fibo 為例，def 後面加的 fibo( ) 為這個動作的名字（函式名稱），括弧內的 n 為傳入的參數。所以當我們呼叫 fibo(10) 的時候，就會把 n 當作 10 去執行動作。

而 return 是為動作賦值，所以當 n 不是 0 或 1 時，fibo(n) = fibo(n-1) + fibo(n-2)，剛好等於它的定義。

所以在上面的程式碼中，當我們執行 print(fibo(10)) 時，就會執行 def 後面的五行程式碼，並把 10 作為 n 執行，最後把它 return 的值印出來。

但根據費波那契數列的定義，要知道第 n 項，我們就需要知道第 n-1 項與第 n-2 項，於是在程式碼中我們可以看到，在 n 不等於 0 或 1 時，fibo( ) 函式就會呼叫函式自己，只是這次是想要來計算第 n-1 項與第 n-2 項，所以就呼叫 fibo(n-1) 與 fibo(n-2)。

而要如何知道第 n-1 項是多少呢？我們這時就需要知道第 n-2 與第 n-3 項，如此類推，最後直到我們想要知道的項為第 0 項與第 1 項時，因為這兩項已經被定義了，所以我們就能一一解答前面的所有項了。

還是有點抽象嗎？讓我們以計算 n=5 時的費波那契數列為例，他在進行函式執行時的呼叫順序如下：

每一項都會按照定義往前呼叫它的前兩項。

從上面的圖可以觀察到，每一次函式往下的呼叫，最後都會停在 F(1) 或 F(0)，因為這兩項是唯一在計算費波那契數列時唯一先被定義的。因此找到這兩項後，就可以開始往前加總出其他項的值，而往前加總的順序如下：

每一項在呼叫到 F(1) 或 F(0) 後，才會往回推算到該項。

了解了費式數列遞迴程式碼如何運作後，老樣子我們要開始分析他的時間複雜度。

費氏數列的時間複雜度

最簡單理解時間複雜度的方法就是直接使用觀察法。從上面的圖我們可以看到，每往下一層，每一項需要呼叫的次數就變成 2 倍，像 F(5) 要呼叫 F(4) + F(3) 、F(3) 要呼叫 F(2) + F(1) 等等。

而要找到數列的第 5 個數，我們需要的層數是剛好是 5 層，而推展到第 n 個數時，我們剛好需要 n 層。這個部分如果有點抽象的話，可以直接觀察上面的例子，圖中每一層的最左邊那項，是從 F(n) 一路遞減到 F(1)，這樣剛剛好會是 n 層。

整理上面兩段如下，我們就可以求出最後時間複雜度約等於為 O(2^n)。

• 每往下一層，步驟數變 2 倍
• 總共有 n 層
• 時間複雜度：O(2^n)

註：有些讀者可能會有疑問，觀察上面的圖，並不是每個數都會呼叫到 n 層，越往圖的右邊呼叫的層數越少。經過神秘的數學運算，最後時間複雜度其實是 1.6180339887^n （那一串數字是大名鼎鼎的黃金比例），但簡單起見，我們比較常用 O(2^n) 去理解。

同場加映：如何加速計算費氏數列的演算法

在上面我們提到過，時間複雜度 O(2^n)，在實務上非常的慢。因此，我們就要來試著改善上面的演算法，看看能不能讓他加速一點。

首先，我們還是要先使用觀察大法，重新檢視上面進行函式執行時的呼叫圖。我們可以輕鬆發現，圖中有很多地方是被重複計算的。例如：我們計算了 F(3) 兩次、F(2) 三次，而這些重複的部分就是拖慢演算法的元兇。

那要如何減少重複計算呢？我們可以「用空間換取時間」，把每一個算過的值都用一個大表依序記下來。這樣當我們想要知道 F(3) 是多少時，我不用重新計算 F(2)+F(1)，只要去大表上找到 F(3) 的答案就好。讓我們以計算 F(10) 為例：

而上面這個方法的時間複雜度為多少呢？我們可以很快心算一下，算每一項的同時我們需要去讀取前兩項的值，並把它加起來，總共需要三個步驟。而我們總共需要算 n-1 次，所以總共的步驟數是 3(n-1) 次，只看最高次方項並拔掉係數後，我們就可以得到加速後的時間複雜度：O(n)。

在程式碼的實作中，我們可以藉由不斷更新大表的數字已達到節省空間的效果，簡單實作計算費氏數列第十項的程式碼如下

table = [0]*3
table[0] = 0
table[1] = 1
​
for i in range(2,11):
    table[2] = table[1] + table[0]
    table[0] = table[1]
    table[1] = table[2]
​
print(table[2])

小結

在這篇文章中，我們先瞭解了何謂費氏數列，並透過費氏數列瞭解了基本遞迴的定義以及所需的時間。接著，我們透過以「空間換取時間」的方式，加速了計算費氏數列的演算法，並將時間複雜度從 O(2^n) 進步到了 O(n)。

【AppWorks School Batch #12 限時招生中】
AppWorks School 將開設 Android、iOS、Front-End 與 Backend Class 四個不同技能的訓練班次，全程免費，透過線上學習 4 週，駐點集訓 16 週的專案導向訓練，幫助你成為軟體工程師。
歡迎想成為軟體工程師的朋友，把握機會申請，報名到 7/22 23:59 截止喔！～https://bit.ly/2BUQmvn

想要準時收看新文章嗎？快追蹤 AppWorks School 的粉專與 Medium Publication 吧！

AppWorks School

嗨，我是程維，目前在美國 Google 擔任軟體工程師。如果你對入門機器學習、深度學習、人工智慧和大語言模型有興趣，我目前在準備一系列入門的文章。歡迎在這個網頁表單輸入你的電子信箱，我會在寫好的第一時間將文章寄送給你。