遞迴 (Recursive) 介紹與經典題型

介紹遞迴的原理,與經典題型:最大公因數 (GCD)、費波納契數列 (Fibonacci Sequence)、河內塔 (Hanoi Tower)、N 個字元的排列組合。

遞迴

遞迴 (Recursive) 是程式中包含自我呼叫 (self-calling)。

1. 當程式遇到 recursive call 時,必須保存當時的執行狀態;即 push 需要保存的內容到 stack memory 中:

  • 參數值 (e.g. x 值)
  • 區域/暫存變數值 (e.g. y 值)
  • 返回位址 (return address),紀錄遞迴呼叫完成後、下一個可執行的程序是什麼

2. 接下來,go to 程式開端執行

3. 若執行遇到 end 敘述時,則:

由於 Stack 空間有限,若又不斷 push 的話就會爆掉,造成所謂的「Stack Overflow」:Recursive 所需的 Stack 空間= (每次 push 的量) * (recursive call 次數)

另外,Push/Pop 執行的時間即是一個損耗,所以 Recursive 相當花時間。

 

Recursive 和 Iterative 的比較

目前學者已證明了——任何一個問題的解決方式,必存在 Recursive 和 Iterative 兩種形式;也就是說,解決同一個問題,可以有遞迴和非遞迴的兩種解法。

從遞迴轉換到非遞迴的程式有一個 SOP 流程可以轉換。但從非遞迴到遞迴沒有 SOP 流程,只能從「理論上」知道一定可以成功轉換過去。

舉例來說,計算一個數字的階乘 (Factorial):

可以有兩種寫法:

可以看到同樣計算 5! = 120 ,Iterative 版本所需的時間更少。至於兩種方式何種較佳呢?這就牽涉到效能 (空間、時間) 的分析啦!

  • Recursive 的優缺
  1. 優:程式碼較為精簡
  2. 優:區域 (暫存) 變數較少
  3. 優:佔用的儲存空間較少
  4. 缺:程式執行的時間較長、較無效率
  5. 缺:需要額外的 Stack 支持

 

  • Iterative 的優缺
  1. 優:程式執行的時間較短 (不用額外處理 push/pop)
  2. 優:不需額外的 Stack 支持
  3. 缺:程式碼較冗長
  4. 缺:區域 (暫存) 變數較少
  5. 缺:佔用的儲存空間較大

 

經典 RECURSIVE 題型

1. 最大公因數

利用輾轉相除法:

 

 

2. FIBONACCI 數列

一個有名的數列 Fibonacci 數列定義如下:

這個數列在 13 世紀初由義大利比薩 (Pisa) 一位叫李奧納多 (Leonardo) 的人所提出:

  1. 小兔出生後兩個月就能長成大兔,可以生小兔。
  2. 可生育的大兔子每個月可以生一對小兔,而且剛好是雄雌各一。
  3. 兔子永生不死。

首幾個 Fibonacci 數是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

RECURSIVE VERSION

ITERATIVE VERSION

DP (DYNAMIC PROGRAMMING) VERSION

在計算 Recursive 題目時,會有蠻多重複的計算,比如在計算 F(4) 時得算出 F(3) / F(2) / F(1) /F(0),但計算 F(3) 時又另外把 F(2) / F(1) /F(0) 重複計算…。

因此我們使用 Dynamic Programming 的技巧來求 Fibonacci 數列,也就是使用一個一維陣列來儲存之前計算過的成果。

可以發現相同的結果:F(10) = 55,Recursive、Iterative、Dynamic Programming 三個版本的時間差異是由大到小。

遞迴的 Fibonacci 數列的時間會這麼長,原因是因為先前算過的內容得重新再算一次、太多冗餘的計算。如果改成 Iterative 版本或 DP 版本就會更有效率。

 

3. 河內塔問題

欲將 A 柱上的 n 個盤子搬移到 C 柱,但必須遵守以下規則:每次只能移動一個圓盤,且大盤不能疊在小盤之上。

遞迴關係式:T(n) = T(n-1) + T(1) + T(n-1),且 T(1) = 1 ;則 T(n) = 2*T(n-1) + T(1) ,解出 T(n) 為 2^n -1。

 

4. 列印 n 個字元的排列組合 (Permutations)

 

 

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *