[algorithms] Recursion 遞迴

視覺化概覽

flowchart TD
    A["呼叫 factorial(4)"] --> B{"n <= 1？\nBase Case"}
    B -->|"否"| C["推入 Stack：4 × factorial(3)"]
    C --> D{"n <= 1？"}
    D -->|"否"| E["推入 Stack：3 × factorial(2)"]
    E --> F{"n <= 1？"}
    F -->|"否"| G["推入 Stack：2 × factorial(1)"]
    G --> H{"n <= 1？"}
    H -->|"是 ✓"| I["回傳 1"]
    I --> J["彈出 Stack：2 × 1 = 2"]
    J --> K["彈出 Stack：3 × 2 = 6"]
    K --> L["彈出 Stack：4 × 6 = 24"]

什麼是遞迴？

函數呼叫自己。

void countdown(int n) {
    if (n == 0) return;  // 終止條件
    System.out.println(n);
    countdown(n - 1);    // 呼叫自己
}

遞迴的兩個要素

1. Base Case（終止條件）

沒有終止條件 = 無限迴圈 = Stack Overflow！

// 錯誤：沒有終止條件
void bad(int n) {
    bad(n - 1);  // 永遠不會停
}
 
// 正確：有終止條件
void good(int n) {
    if (n <= 0) return;  // Base Case
    good(n - 1);
}

2. Recursive Case（遞迴呼叫）

每次呼叫都要往 Base Case 靠近。

factorial(5)
  → 5 × factorial(4)
    → 4 × factorial(3)
      → 3 × factorial(2)
        → 2 × factorial(1)
          → 1  (Base Case!)
        ← 2 × 1 = 2
      ← 3 × 2 = 6
    ← 4 × 6 = 24
  ← 5 × 24 = 120

經典遞迴問題

1. 階乘

n! = n × (n-1) × ... × 1
5! = 5 × 4 × 3 × 2 × 1 = 120

int factorial(int n) {
    if (n <= 1) return 1;      // Base Case
    return n * factorial(n-1);  // Recursive Case
}

2. 費波那契

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

0, 1, 1, 2, 3, 5, 8, 13, 21...

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

3. 河內塔

把 n 個盤子從 A 移到 C，一次只能移一個，大的不能放在小的上面。

n=3 的解法：
1. 把上面 2 個從 A 移到 B
2. 把最大的從 A 移到 C
3. 把 2 個從 B 移到 C

步驟：A→C, A→B, C→B, A→C, B→A, B→C, A→C (7步)

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        move(from, to);
        return;
    }
    hanoi(n-1, from, aux, to);  // 移到輔助柱
    move(from, to);              // 移最大的
    hanoi(n-1, aux, to, from);  // 從輔助柱移回
}

4. 二分搜尋

int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;  // 找不到
 
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target)
        return binarySearch(arr, target, left, mid-1);
    else
        return binarySearch(arr, target, mid+1, right);
}

5. 排列組合

產生 [1,2,3] 的所有排列：

[1,2,3] [1,3,2]
[2,1,3] [2,3,1]
[3,1,2] [3,2,1]

void permute(int[] arr, int start) {
    if (start == arr.length) {
        print(arr);
        return;
    }
    for (int i = start; i < arr.length; i++) {
        swap(arr, start, i);      // 選擇
        permute(arr, start + 1);  // 遞迴
        swap(arr, start, i);      // 回溯
    }
}

遞迴 vs 迴圈

比較	遞迴	迴圈
可讀性	通常更直觀	可能較複雜
效能	有函數呼叫開銷	較快
記憶體	用 Stack，可能溢出	固定空間
適用	樹、圖、分治	簡單迭代

// 遞迴版
int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}
 
// 迴圈版
int sum(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

尾遞迴優化

尾遞迴：遞迴呼叫是函數的最後一個操作。

// 一般遞迴（不是尾遞迴）
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n-1);  // 還要做乘法
}
 
// 尾遞迴
int factorial(int n, int acc) {
    if (n <= 1) return acc;
    return factorial(n-1, n * acc);  // 直接回傳
}

某些語言會優化尾遞迴，避免 Stack Overflow。

回溯法 (Backtracking)

遞迴 + 還原狀態 = 回溯

// 走迷宮
void solve(int x, int y) {
    if (isGoal(x, y)) {
        found = true;
        return;
    }
 
    for (每個方向) {
        if (canMove(x, y, 方向)) {
            mark(x, y);           // 標記走過
            solve(newX, newY);    // 遞迴
            unmark(x, y);         // 回溯（還原）
        }
    }
}

遞迴思考步驟

1. 定義問題：這個函數要解決什麼？
2. 找 Base Case：什麼時候不需要遞迴？
3. 找 Recursive Case：怎麼把問題變小？
4. 相信遞迴：假設子問題已經解決

常見錯誤

// 1. 忘記 Base Case
void bad1(int n) {
    bad1(n - 1);  // Stack Overflow!
}
 
// 2. 沒有往 Base Case 靠近
void bad2(int n) {
    if (n == 0) return;
    bad2(n);  // n 沒有變小！
}
 
// 3. 回傳值忘記接
int bad3(int n) {
    if (n == 0) return 0;
    bad3(n - 1);  // 忘記 return！
}

時間複雜度

問題	時間複雜度
階乘	O(n)
費波那契（無優化）	O(2^n)
二分搜尋	O(log n)
河內塔	O(2^n)
排列	O(n!)

相關檔案

• Java 實作：Recursion.java
• 視覺化：recursion.html