接下來想要緩慢的把自己的 CS 相關基礎補上，多多接觸寬廣的技術知識，就先從遞迴開始吧！
🐳 遞迴的種類
如果一個 function 裡面有 self-calling 的敘述，便稱為遞迴，遞迴概略可以分為三個種類，分別是：
- Direct Recursion
- Indirect Recursion
- Tail Recursion
下面舉一些簡單的例子來說明這三個遞迴。
🦀 Direct Recursion
Direct Recursion，直接遞迴，應該蠻好理解的。如果某個 function 在 function 內部呼叫自己，就可以稱為直接遞迴。可以參考下面的 psuedo code：
void directRecursionFunction()
{
// some code...
directRecursionFunction();
// some code...
}
🦀 Indirect Recursion
Indirect Recursion，間接遞迴，意思是指多個 module 之間，彼此互相呼叫，形成 calling cycle。例如：假設目前有三個 function：module A、module B、module C，這三個 function 彼此互相呼叫，便會形成間接遞迴，如下圖：
像上面那種 function 互相 call 來 call 去，互相高度依賴的狀況（高耦合），盡量不要在實際開發中寫出來，會很可怕。
🦀 Tail Recursion
Tail Recursion，尾端遞迴，其實是直接遞迴的一種，只是在 recursion 之後，下一個可執行的敘述就是 END 敘述。會特別把這個種類分出來是因為這種遞迴可以在 compiler 裡面做到最佳化。（最佳化的意思，某種程度上可以理解成「將遞迴改成非遞迴」）
🐳 Recursion v.s. Iteration(Non-recusrion)
- 任何問題的解法必定可以用兩種演算法去解決：遞迴與非遞迴。
- 遞迴與非遞迴演算法兩者可以互相轉換
- 遞迴改為非遞迴，有標準 SOP
- 非遞迴改回遞迴，沒有標準 SOP（需要靈感）
示意圖
比較表
| 遞迴 | 非遞迴 | |
|---|---|---|
| 程式碼 | 較精簡 | 較冗長 |
| 區域變數、暫存變數 | 使用很少或是沒有 | 使用量多 |
| 表達問題的能力 | powerful | weak |
| 除錯 | 困難 | 容易 |
| 程式執行時間 | 較久，比較沒有效率 | 較短，較有效率 |
| memory stack 空間 | 需要額外的 stack 空間支持，所以執行時需要較多的動態空間 | 無需 stack support |
🐳 題目練習
🦀 Factorial N! 階乘
Question 1: Write an Interative function Fac(N) or pseudo code for N!
function fac(n) {
let result = 1;
for (let i = 1; i <= n; i++>) {
result = result * i;
}
return result;
}
Question 2: Write a Recursive function Fac(N) or pseudo code for N!
先把階乘的遞迴數學定義寫出來：
然後再寫出遞迴的程式碼：
function fac(n) {
if (n === 0) {
return 1;
} else {
return fac(n-1) * n;
}
}
解遞迴相關問題的訣竅：先想出遞迴的數學定義，再把數學定義轉換成程式碼！
🦀 Fibonacci Number
Definition
Question 1: Write a Recurisive function for Fib(N)
function fib(n) {
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
return fib(n-1) + fib(n-2);
}
Quesiton 2: Write a Interative function for Fib(N)
function fib(n) {
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else {
let a = 0;
let b = 1;
let c;
for (let i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
🦀 Greatest Common Divisor (GCD) 最大公因數
Definition
用輾轉相除法來計算兩個數字（A, B）的最大公因數，定義如下：
Write the recursive code for GCD(A, B)
function gcd(a, b) {
if (a % b === 0) return b;
return gcd(b, a % b);
}
🦀 Tower of Hanoi 河內塔
題目敘述
有三個柱子，假設分別叫做 A、B、C，其中 A 柱子上有 n 個大小不同的盤子，這些盤子從上到下按照大小排放，最上面的盤子最小，最下面的盤子最大，現在要把這些盤子從 A 柱子移到 C 柱子，但必須遵守以下規則：
- 每次只能移動一個盤子
- 大的盤子不能放在小的盤子上面
請把所有的移動步驟都 print 出來。
解題思路
A B C
│ │ │
│ │ │
│ │ │
1 ┌─┼─┐ │ │
2 ┌┼┼┼┼┼┐ │ │
3 ┌┼┼┼┼┼┼┼┐ │ │
─┴───────┴─ ────┴──── ────┴────
先從例子開始想，假設目前有 A、B、C 三個柱子，然後有 3 個盤子在 A 柱子上面，則步驟如下：
- move disk 1 from A to C
- move disk 2 from A to B
- move disk 1 from C to B
- move disk 3 from A to C
- move disk 1 from B to A
- move disk 2 from B to C
- move disk 1 from A to C
把步驟分成三個區塊來看：
- 第 1. ~ 3. 步驟是把 1 ~ 2 號的盤子都先從 A 柱子移到 B 柱子
- 第 4. 步驟是把最後一個第 3 號盤子直接從 A 柱子移到 C 柱子
- 接下來是把 B 柱子上的盤子都移到 C 柱子
例外情況：如果只有一個盤子的話，就直接從 A 柱子搬到 C 柱子就可以了。
function hanoi(n, from, to, via) {
if (n === 1) {
console.log(`move disk 1 from ${from} to ${to}`);
} else {
hanoi(n - 1, from, via, to); // 先把 n - 1 個盤子都移到中間的柱子
console.log(`move disk ${n} from ${from} to ${to}`); // 把最下面的盤子移到目標柱子
hanoi(n - 1, via, to, from); // 再把剩下的 n - 1 個盤子移到目標柱子
}
}
河內塔的遞迴定義
把上面提到的步驟用數學式來表示， 表示移動 個盤子時程式所需的執行次數，如果解出 就表示解出了這個 function 的時間複雜度：
解 ，用展開代入法：
Top comments (0)