C 語言遞迴：階乘 Factorial

學習目標

理解遞迴 (Recursion) 的基本概念
掌握階乘的遞迴定義和實作
理解遞迴的執行過程
了解遞迴的優缺點
能夠追蹤遞迴函數的執行

1. 遞迴的基本概念

1.1 什麼是遞迴？

遞迴 (Recursion) 是指函數直接或間接地呼叫自己。

1.2 遞迴的兩個要素

基礎情況 (Base Case): 遞迴終止的條件
遞迴情況 (Recursive Case): 將問題分解為更小的相同問題

1.3 遞迴 vs 迭代

遞迴: 函數呼叫自己
迭代: 使用迴圈重複執行

2. 階乘的定義

2.1 數學定義

階乘 (Factorial) 的數學定義：

n! = n × (n-1) × (n-2) × ... × 2 × 1

特殊情況:

0! = 1
1! = 1

2.2 遞迴定義

階乘也可以用遞迴方式定義：

factorial(n) = {
    1,              if n = 0 or n = 1
    n × factorial(n-1),  if n > 1
}

2.3 範例

5! = 5 × 4 × 3 × 2 × 1 = 120
5! = 5 × 4! = 5 × 24 = 120
4! = 4 × 3! = 4 × 6 = 24
3! = 3 × 2! = 3 × 2 = 6
2! = 2 × 1! = 2 × 1 = 2
1! = 1

3. 遞迴實作

3.1 C 語言程式碼

int factorial(int n) {
    // 基礎情況
    if (n == 0 || n == 1)
        return 1;

    // 遞迴情況
    return n * factorial(n - 1);
}

3.2 執行過程追蹤

計算 factorial(5) 的執行過程：

factorial(5)
  → 5 * factorial(4)
    → 4 * factorial(3)
      → 3 * factorial(2)
        → 2 * factorial(1)
          → 1 (基礎情況，返回 1)
        ← 2 * 1 = 2
      ← 3 * 2 = 6
    ← 4 * 6 = 24
  ← 5 * 24 = 120

3.3 詳細執行步驟

呼叫層級	n 的值	執行內容	返回值
1	5	`5 * factorial(4)`	等待...
2	4	`4 * factorial(3)`	等待...
3	3	`3 * factorial(2)`	等待...
4	2	`2 * factorial(1)`	等待...
5	1	`return 1`	1
4	2	`2 * 1`	2
3	3	`3 * 2`	6
2	4	`4 * 6`	24
1	5	`5 * 24`	120

3.4 呼叫堆疊 (Call Stack)

[factorial(1)]  ← 頂部（當前執行）
[factorial(2)]
[factorial(3)]
[factorial(4)]
[factorial(5)]  ← 底部（最初呼叫）

4. 迭代版本（對比）

4.1 使用迴圈的實作

int factorialIterative(int n) {
    int result = 1;

    for (int i = 1; i <= n; i++) {
        result = result * i;
    }

    return result;
}

4.2 執行過程

計算 factorialIterative(5):

i = 1: result = 1 * 1 = 1
i = 2: result = 1 * 2 = 2
i = 3: result = 2 * 3 = 6
i = 4: result = 6 * 4 = 24
i = 5: result = 24 * 5 = 120
返回: 120

5. 遞迴的優缺點

5.1 優點

程式碼簡潔: 遞迴版本通常比迭代版本更簡潔
直觀: 符合問題的數學定義
易於理解: 對於某些問題，遞迴思路更自然

5.2 缺點

空間開銷: 每次遞迴呼叫都需要在堆疊中儲存資訊
時間開銷: 函數呼叫有額外的開銷
堆疊溢位: 深度遞迴可能導致堆疊溢位
效能: 通常比迭代版本慢

5.3 範例：堆疊溢位

// 計算 factorial(10000) 可能導致堆疊溢位
int result = factorial(10000);  // 錯誤！

6. 尾遞迴優化 (Tail Recursion)

6.1 什麼是尾遞迴？

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

6.2 尾遞迴版本的階乘

int factorialTail(int n, int acc) {
    // acc 是累積器 (accumulator)
    if (n == 0 || n == 1)
        return acc;

    return factorialTail(n - 1, n * acc);
}

// 包裝函數
int factorial(int n) {
    return factorialTail(n, 1);
}

6.3 執行過程

計算 factorial(5) = factorialTail(5, 1):

factorialTail(5, 1)
  → factorialTail(4, 5)
    → factorialTail(3, 20)
      → factorialTail(2, 60)
        → factorialTail(1, 120)
          → 120 (基礎情況)

6.4 尾遞迴的優點

某些編譯器可以將尾遞迴優化為迭代
減少堆疊空間使用

7. 除錯技巧

7.1 加入除錯輸出

int factorial(int n) {
    printf("呼叫 factorial(%d)\n", n);

    if (n == 0 || n == 1) {
        printf("返回 1\n");
        return 1;
    }

    int result = n * factorial(n - 1);
    printf("factorial(%d) = %d\n", n, result);
    return result;
}

輸出 (factorial(5)):

呼叫 factorial(5)
呼叫 factorial(4)
呼叫 factorial(3)
呼叫 factorial(2)
呼叫 factorial(1)
返回 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120

7.2 檢查基礎情況

確保基礎情況正確，否則會導致無限遞迴：

// 錯誤範例：缺少基礎情況
int factorial(int n) {
    return n * factorial(n - 1);  // 無限遞迴！
}

8. 常見錯誤

8.1 缺少基礎情況

// 錯誤
int factorial(int n) {
    return n * factorial(n - 1);
}

8.2 基礎情況錯誤

// 錯誤：0! 應該是 1，不是 0
int factorial(int n) {
    if (n == 0)
        return 0;  // 錯誤！
    return n * factorial(n - 1);
}

8.3 遞迴情況錯誤

// 錯誤：應該是 n-1，不是 n+1
int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * factorial(n + 1);  // 錯誤！會無限遞迴
}

9. 練習題

練習題 1

追蹤 factorial(4) 的執行過程，寫出每一步的返回值。

解答：

factorial(4)
  → 4 * factorial(3)
    → 3 * factorial(2)
      → 2 * factorial(1)
        → 1
      ← 2 * 1 = 2
    ← 3 * 2 = 6
  ← 4 * 6 = 24

返回值序列: 1 → 2 → 6 → 24

練習題 2

實作一個函數，計算階乘並使用迭代版本。