演算法筆記：遞迴（Recursion）

Published in

Traveling Light Taipei

4 min readAug 24, 2020

遞回函式（recursive function）簡單來說就是在一個函式當中再去呼叫它自己，其中一個實際的範例就是費氏數列。

費波那契數列

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

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

function fibo(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } 
  return fibo(n-1) + fibo(n-2)
}fibo(5)

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

最簡單理解時間複雜度的方法就是直接使用觀察法。從上面的圖我們可以看到，每往下一層，每一項需要呼叫的次數就變成 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)。

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

之所以能夠透過遞回函式，是因為函式堆疊（stack）在執行時有一個特性，當某個函式呼叫另一個函式時，需要等到裡面的函式執行完產生結果後，才會繼續回來執行自己的函式內容，而這樣的情況也被稱作 後進先出（Last in First Out, LIFO）。

事實上遞迴的時間複雜度相當高，並不會實際使用在計算中，需要搭配動態運算等方法把已經計算過的數值記錄下來，優化計算時間，這部分下篇筆記會說明。