遞迴（Recursion）

遞迴（recursion）

一個函式持續自我呼叫的過程，稱為「遞迴」，如果沒有設終止條件，則遞迴將永無止盡。

遞迴範例一：等差級數（arithmetic series）

若要以 Python 撰寫「等差級數」的程式碼，可以有下列三種方式：

1. 等差級數公式解

直接把 n=5 代入程式碼的等差級數公式中，得 (5·(5+1))/2=15。

2. 迴圈解

設定起始值 sum 為 0，只要 i<(n+1)，就進行賦值運算，逐次將 sum 加上 i=1、2、3...，直到 i=n 為止。

如果 i=5、起始值 sum 為 0，迴圈內的運行步驟如下：

1. i=1、sum=0，sum+i=0+1=1，sum 經賦值運算變成 1。
2. i=2、sum=1，sum+i=1+2=3，sum 經賦值運算變成 3。
3. i=3、sum=3，sum+i=3+3=6，sum 經賦值運算變成 6。
4. i=4、sum=6，sum+i=4+6=10，sum 經賦值運算變成 10。
5. i=5、sum=10，sum+i=5+10=15，sum 經賦值運算變成 15。
6. i=6 時已經超出迴圈範圍，因此跳出迴圈，回傳的 sum 值為 15。

3. 遞迴解

每一次的計算都套用函式本身以 (n-1) 為變數所求之結果，直到 n 變成 1 為止。

1. 輸入 5 時，5≠1，因此回傳 (5+Sum(4)) 的值；
2. 4≠1，因此回傳 (4+Sum(3)) 的值；
3. 3≠1，因此回傳 (3+Sum(2)) 的值；
4. 2≠1，因此回傳 (2+Sum(1)) 的值；
   1=1，符合 if 中的條件，因此不進入下一次遞迴，直接得 Sum(1)=1，這時就可以回推：
5. n=2 時，(2+Sum(1))=(2+1)=3；
6. n=3 時，(3+Sum(2))=(3+3)=6；
7. n=4 時，(4+Sum(3))=(4+6)=10；
8. n=5 時，(5+Sum(4))=(5+10)=15。

在 Sum 這個函數中，再次出現「Sum」函數（黃框處），每一輪 Sum 的運算都要用到前一輪 Sum 的運算結果，這種關係就稱為「遞迴」。

如果沒有加上終止條件「n==1」會怎麼樣呢？

不僅沒有跑出答案，左方黃框處還多了一個星號，代表「核心忙碌中」。明明有在算卻什麼結果也沒顯示，為什麼？

那到了 n=1 時，還能計算 (1+(Sum(0))；n=0 時，還能往下計算 (1+(Sum(-1))； n=-1 時，還能繼續往下計算 (1+(Sum(-2))...，就這樣一路遞迴下去、沒完沒了，有些電腦很可能承受不住無止盡的運算就直接當機。

遞迴範例二：階乘（factorial）

代表一個正整數乘以小於該數所有正整數的積，記為「!」，例如 5!=5·4·3·2·1=120。

1. 迴圈解

設定起始值為 1，只要 i<(n+1)，就進行賦值運算，讓新的值逐次乘上 1、2、3...，直到 i=n 為止。

如果 i=5、起始值 result 為 1，迴圈內的運行步驟如下：

1. i=1、result=1，i·result=1·1=1，result 經賦值運算變成 1。
2. i=2、result=1，i·result=2·1=2，result 經賦值運算變成 2。
3. i=3、result=2，i·result=3·2=6，result 經賦值運算變成 6。
4. i=4、result=6，i·result=4·6=24，result 經賦值運算變成 24。
5. i=5、result=24，i·result=5·24=120，result 經賦值運算變成 120。
6. i=6 時已經超出迴圈範圍，因此跳出迴圈，回傳的 result 值為 120。

2. 遞迴解

先設立終止條件 n==1，1!=1，因此輸入的 n=1 時，回傳的值為 1。

1. 輸入 5 時，5≠1，因此回傳 (5·factorial(4)) 的值；
2. 4≠1，因此回傳 (4·factorial(3)) 的值；
3. 3≠1，因此回傳 (3·factorial(2)) 的值；
4. 2≠1，因此回傳 (2·factorial(1)) 的值；
   1=1，符合 if 中的條件，因此不進入下一次遞迴，直接得 factorial(1)=1，這時就可以回推：
5. n=2 時，(2·factorial(1))=(2·1)=2；
6. n=3 時，(3·factorial(2))=(3·2)=6；
7. n=4 時，(4·factorial(3))=(4·6)=24；
8. n=5 時，(5·factorial(4))=(5·4)=120。

遞迴範例三：輾轉相除法（Euclidean algorithm）

輾轉相除法又稱為「歐幾里得演算法」，可以用來求兩個數的「最大公因數（greatest common divisor）」，其概念如下，詳細可參考 Stepp 學院影片：

對於一個被除數 a、除數 b，根據除法定理，可以寫成如下形式：
a = bq + r 或 a / b = q…r

q 為商數、r 為餘數；「輾轉相除法」會將除數轉為下一輪運算的被除數、餘數轉為下一輪運算的除數，直到餘數變成 0 為止，而當餘數為 0 時，當時的被除數就是兩數的「最大公因數」，詳細過程如下：

1. a % b = r₁
2. b % r₁ = r₂
3. r₁ % r₂ = r₃
4. r₂ % r₃ = r₄

這樣的過程將持續到等號右方的餘數變成 0 為止，現假設 r₄=0，則代表第 4. 式被除數 r₂ 是 a、b 兩數的最大公因數。

由上述計算過程，我們可以得知，不論是用迴圈或遞迴解，都圍繞著下列三個核心概念：

1. 每一輪的除數將變成下一輪計算的被除數
2. 每一輪的餘數將變成下一輪計算的除數
3. 某輪計算的除數（即上一輪計算的餘數）為 0 時，運算終止，該輪計算的被除數（即上一輪運算的除數）即為最大公因數

這些核心概念分別對應「迴圈解」與「遞迴解」的 Python 程式碼如下：

迴圈解：

遞迴解：

遞迴範例四：費氏數列（Fibonacci sequence）

「費氏數列」可用函數 Fibonacci(n) 表示如下：

1. Fibonacci(0)=0
2. Fibonacci(1)=1
3. n≥2 時，Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)

從 n=2 開始，每一次的運算都要用到前兩次的運算結果，是個非常經典的遞迴案例，用 Python 程式碼呈現如下：

設定終止條件 n=0 與 n=1 後，即可開始運行後續的遞迴計算，得到 n=2 開始每一項的值。惟此一運算方式的大 O 標記為 O(2ⁿ)，時間複雜度很高，不適用於 n 很大的情況，可用「以空間換取時間」的方式調整，詳細說明可參考本篇 Medium。

遞迴範例五：河內塔（Tower of Hanoi）

相傳在越南河內的某間寺院內，一共有三根柱子，其中一根柱子有 64 個盤子，僧侶依照下列規則將盤子依序移往第三根柱子，當 64 個盤子全部都移到第三根柱子時，世界就會毀滅。

1. 規則一：一次只能移動一個盤子。
2. 規則二：整個移動過程中，小盤子必在大盤子之上。

試問把 64 個盤子全部搬完至少需要幾個步驟？

我們可以先把盤子數量減少，再慢慢找出規則。現假設三根柱子分別為 A、B、C。

一個盤子：共一個步驟

1. 將唯一的盤子從 A 移到 C。
   

兩個盤子：共三個步驟

1. 將第 1 個盤子從 A 移到 B。
2. 將第 2 個盤子從 A 移到 C。
3. 將 B 的第 1 個盤子移到 C。
   

三個盤子：共七個步驟

1. 將第 1 個盤子從 A 移到 C。
2. 將第 2 個盤子從 A 移到 B。
3. 將 C 的第 1 個盤子移到 B，放在第 2 個盤子上。
4. 將第 3 個盤子從 A 移到 C。
5. 將 B 的第 1 個盤子移回 A。
6. 將 B 的第 2 個子移到 C，放在第 3 個盤子上。
7. 將 A 的第 1 個盤子放到 C 的第 2 個盤子上。
   

現在我們來比較三種不同盤數的狀況，看是否有特殊的規律可循：

• 將一個盤子從某根柱子移動到另一根柱子，共要 1 個步驟，即 2¹-1 次。
• 將兩個盤子從某根柱子移動到另一根柱子，要經歷兩輪「移動一個盤子」的過程（第 1. 步先把第 1 個盤子從 A 放到 B、第 3. 步再把第 1 個盤子從 B 放到 C），外加第 2. 步將第 2 個盤子從 A 移到 C 一次，共要 (1+1)+1=3 個步驟，即 2²-1 次。
• 將三個盤子從某根柱子移動到另一根柱子，要經歷兩輪「移動兩個盤子」的過程（第 1.~3. 步把第 1&2 兩個盤子先都從 A 放到 B，第 5~7 步再把第 1&2 兩個盤子都從 B 放到 C），外加第 4 步將第 3 個盤子從 A 移到 C 一次，共要 (3+3)+1=7 個步驟，即 2³-1 次。

同樣地，當有四個盤子時，也會經歷兩次「移動三個盤子」的過程，外加將最大的第 4 個盤子從 A 移到 C 一次，共要 (7+7)+1=15 個步驟，即 2⁴-1 次，依此類推，到有 n 個盤子時，共要移動 2ⁿ-1 次，步驟可以這樣理解：

• 將 n-1 個盤子從 A 移到 B
• 將最大的第 n 個盤子從 A 移到 C
• 將 n-1 個盤子從 B 移到 C
  

移動 n 個盤子的總次數為「移動 (n-1) 個盤子的總次數」·2+1，用 Python 呈現如下：

河內塔共有 64 個盤子，一共需要 2⁶⁴-1 個步驟才能全部移動完畢，相當於 1.84 x 10¹⁹ 次，就算一秒移動一塊圓盤，也要超過 5849 億年，而根據推測，目前宇宙的年齡不過 137 億年，看來我們可不必擔心在有生之年看到盤子搬完、世界毀滅的那一天。

顯示河內塔盤子移動過程

假設三柱為 A、B、C，共有 n=3 個盤子要移動，盤子的編號為 1、2、3，顯示移動過程的程式碼如下：

在「else」段落的程式碼可以向下拆解至 n=1 為止，當中的 A、B、C 三參數順序會改變，移動盤子的過程固定由第一個陣列參數移動到第三個陣列參數，但移出、接收盤子的柱子會依步驟而異。

程式碼運行過程圖示如下，當中的「STEP 1」、「STEP 2」…「STEP 7」可對照上方「三個盤子的河內塔移動過程」圖：

解析解／閉式解（closed-form solution）

遞迴是一個十分耗費運算力的過程，因此，我們會希望使用遞迴之外的其他方法，簡化計算流程。

一、一階線性遞迴關係（linear first-order recurrence relation）

在上述的「等差級數」中，我們知道：

1. A₁=1
2. Aₙ=Aₙ-₁+n，n≥2，n∈N

透過上述關係，我們可以依序找到該數列的值為 1、3、6、10、15…，但若要找第 100 項、第 1000 項、第 10000 項呢？

為了要找到第 100 項，我們得先找第 99 項；為了找第 99 項，還得先找第 98 項...一路找到第 1 項為止，而且在找第 98 項時，電腦不會知道已經在找第 99 項時算過一次第 1~97 項，因此第 1~97 項會全部都重新算一次；在找第 97 項時，第 1~96 項也都會重新計算一次...等到第 1~100 每一項都被算出來時，運算次數十分可觀，更不用說還要找第 1000、甚至第 10000 項。

那麼，是否有不會重複進行運算，就能得到結果的方式呢？

現在我們假設 Aₙ=CAₙ-₁+Gₙ，C 為常數、Gₙ 為數列：

1. 根據遞迴關係，Aₙ-₁=CAₙ-₂+Gₙ-₁，因此可寫成下列形式：
   Aₙ = C[CAₙ₋₂+Gₙ₋₁]+Gₙ = C²Aₙ₋₂+CGₙ₋₁+Gₙ
2. 又 Aₙ-₂=CAₙ-₃+Gₙ-₂，因此又可以寫成如下形式：
   Aₙ = C²(CAₙ₋₃+Gₙ₋₂)+CGₙ₋₁+Gₙ
   = C³Aₙ₋₃+C²Gₙ₋₂+CGₙ₋₁+Gₙ
3. 依此類推，從 Aₙ₋₁ 開始找 (n-1) 次可到 A₁，因此 Aₙ 可寫成下列形式：
   Aₙ = Cⁿ⁻¹A₁+[Gₙ+CGₙ₋₁+C²Gₙ₋₂…+Cⁿ⁻²Gₙ₋₍ₙ₋₂₎]
4. 用 Σ 符號表示括弧內的項目：
   

這就是「一階線性遞迴關係」的公式！

在「等差級數」中，C=1、A₁=1、Gᵢ=2、3、4…，假設要找第 5 項，則可以套此公式得：

展開 Σ，得 (1⁴·1) + (1³·2 + 1²·3+ 1¹·4 + 1⁰·5)=(1)+(2+3+4+5)=15

將Σ展開後剛好跟土法煉鋼的「1+2+3+4+5」算法一模一樣，可以直接套等差級數公式「[n(n+1)]/2」，將 n=5 代入，得答案為 15。

「一階線性遞迴關係」另一範例

等差級數較為特別，另有更為簡易的公式可找到第 n 項，但在其他的一階線性遞迴關係中，上個段落推導出的公式非常實用，跟遞迴相比，可以大幅減少運算量。舉例如下：

1. A₁=1
2. Aₙ=3Aₙ-₁+2，n≥2，n∈N

透過遞迴可以得 A₂ 起為 5、17、53、161、485...，那如果要找第 100、1000、甚至第 10000 項呢？

我們可以透過公式快速找到解答，在這個範例中，C=3、A₁=1、Gᵢ=2、2、2...，假設要找第 5 項，則可以套此公式得：

因為 Gᵢ 為常數，可以提到 Σ 外，再展開 Σ 得 (3⁴·1) + 2·(3³ + 3² + 3¹ + 3⁰)，加號右方再套等比級數公式可得 (81·)+2·[1(1-3⁴)/(1-3)]=161，與用遞迴關係計算的結果相同。

假設要找第 1000 項，只要把 n 以 1000 代入即可，加號右方一樣代入等比級數公式：
A₁₀₀₀ = (3¹⁰⁰⁰⁻¹·1)+2·[1(1–3⁹⁹⁹)/(1–3)]

二、二階線性遞迴關係（linear second-order recurrence relation）

「二階線性遞迴關係」指其數列第 n 項與第 (n-1) 及 (n-2) 項皆有關係，如上文曾提及的「費波那契數」：

1. A₀=0
2. A₁=1
3. Aₙ=Aₙ₋₁+Aₙ₋₂，n≥2，n∈N

我們可以推得 A₂ 起的值依序為 1、2、3、5、8、13…，但如果要找第 100 項、第 1000 項、甚至第 10000 項呢？一樣會因為其遞迴關係耗費大量運算力，可以改用其他方式找到 Aₙ。

根據上個段落「一階線性遞迴關係」公式推導過程，我們知道下列關係：

若 Gₙ=0，則每項 Gᵢ 皆為 0、Σ 內每一項都變成 0，如下：

當 C=A₁ 時，可以得到下列結果：

假設我們新的遞迴關係式也能寫成 Aₙ=Cⁿ 形式，但把 C 改成 r、即 Aₙ=rⁿ，則根據二階遞迴關係，可以推得下列結果：
rⁿ = rⁿ⁻¹+rⁿ⁻²
等號兩側同除以 (n-2) 次方，得下列關係式：
r² = r¹+r⁰ = r¹+1
移項得一元二次方程式與其解如下：
r²-r¹-1 = 0 → r₁ = (1+√5)/2、r₂ = (1-√5)/2
將 r₁=(1+√5)/2 與 r₂=(1-√5)/2、費波那契數 A₀=0 與 A₁=1 分別代入「Aₙ = p·r₁ⁿ + q·r₂ⁿ」，可得：
A₀ = 0 = p+q
A₁ = 1 = [(1+√5)/2]p + [(1-√5)/2]q
由上述兩式解二元一次聯立方程式得 p=1/√5、q=–1/√5。

若要求第 Aₙ 項，則可代入 r₁=(1+√5)/2、r₂=(1-√5)/2、p=1/√5、q=–1/√5 得下列關係式：
Aₙ = p·r₁ⁿ + q·r₂ⁿ
= (1/√5)·[(1+√5)/2]ⁿ + (–1/√5)·[(1-√5)/2]ⁿ

當我們今天要求第 1000 項，只要把 n 以 1000 代入即可：
A₁₀₀₀ = (1/√5)·[(1+√5)/2]¹⁰⁰⁰ + (–1/√5)·[(1-√5)/2]¹⁰⁰⁰

「二階線性遞迴關係」另一範例

1. A₀=3
2. A₁=8
3. Aₙ=3Aₙ₋₁–2Aₙ₋₂，n≥2，n∈N

將上述遞迴關係寫成 Aₙ=rⁿ 形式：
rⁿ = 3rⁿ⁻¹-2rⁿ⁻²
等號兩側同除以 (n-2) 次方，得下列關係式：
r² = 3r¹-2r⁰ = 3r¹-2
移項得一元二次方程式與其解如下：
r²-3r¹+2 = 0 → (r-2)(r-1)=0 → r₁ = 1、r₂ = 2
將 r₁=1 與 r₂=2、A₀=3 與 A₁=8 分別代入「Aₙ = p·r₁ⁿ + q·r₂ⁿ」，可得：
A₀ = 3 = p·1⁰+q·1⁰ = p+q
A₁ = 8 = p·1¹ + q·2¹ = p+2q
由上述兩式解二元一次聯立方程式得 p=–2、q=5。
若要求第 Aₙ 項，則可代入 r₁=1、r₂=2、p=–2、q=5 得下列關係式：
Aₙ = p·r₁ⁿ + q·r₂ⁿ = (–2)·1ⁿ + 5·2ⁿ
當我們今天要求第 1000 項，只要把 n 以 1000 代入即可：
A₁₀₀₀ = (–2)·1¹⁰⁰⁰ + 5·2¹⁰⁰⁰

三、高階線性遞迴關係（linear high order recurrence relation）

現假設有一 K 階線性遞迴關係如下：
Aₙ = rⁿ
rⁿ = C₁·Aₙ₋₁ + C₂·Aₙ₋₂ + … + C₍ₖ₋₁₎·Aₙ₋₍ₖ₋₁₎ + Cₖ·Aₙ₋ₖ
將 Aₙ 以 rⁿ 代入如下：
rⁿ = C₁·rⁿ⁻¹ + C₂·rⁿ⁻² + … + Cₖ₋₁·rⁿ⁻⁽ᵏ⁻¹⁾ + Cₖ·rⁿ⁻ᵏ
將等號右方的式子移至左方如下：
rⁿ – C₁·rⁿ⁻¹ – C₂·rⁿ⁻² – … – Cₖ₋₁·rⁿ⁻⁽ᵏ⁻¹⁾ – Cₖ·rⁿ⁻ᵏ = 0
同除以 rⁿ⁻ᵏ 得下列結果：
rᵏ – C₁·rᵏ⁻¹ – C₂·rᵏ⁻² – … – Cₖ₋₁·rᵏ⁻⁽ᵏ⁻¹⁾ – Cₖ = 0
此時 r₁（即rᵏ⁻⁽ᵏ⁻¹⁾）、r₂、…、rₖ 都是上列方程式的根，設 α₁、α₂、...、αₖ 為任意數，則：
Aₙ = α₁·r₁ⁿ + α₂·r₂ⁿ + ... + αₖ₋₁·r₍ₖ₋₁₎ⁿ + αₖ·rₖⁿ
只要求出 r₁、r₂、…、rₖ，代回方程式求得 α₁、α₂、…、αₖ，即可推得 Aₙ 的解析解。

小結

1. 遞迴：指函式自我呼叫，應設終止條件。
2. 遞迴範例：等差級數、階乘、輾轉相除法、費氏數列、河內塔。
3. 計算遞迴關係可用解析解，減少時間複雜度。