C 語言遞歸實戰：編寫階乘函數 N! 完整代碼與解析

遞歸是函數直接或間接調用自身，解決階乘、斐波那契、樹遍歷等自我相似問題的利器。

階乘遞歸定義

n! = n × (n-1)! (n > 1)
1! = 1（基準情況）

標準實現代碼

#include <stdio.h>

// 遞歸函數
int factorial(int n) {
    if (n == 1)           // 基準情況：遞歸終止條件
        return 1;
    return n * factorial(n - 1);  // 遞歸步驟：問題規模縮小
}

int main() {
    int n;
    printf("請輸入正整數 n: ");
    if (scanf("%d", &n) != 1 || n < 1) {
        printf("輸入無效\n");
        return 1;
    }
    printf("%d! = %d\n", n, factorial(n));
    return 0;
}

執行流程追蹤 (n=4)

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

遞歸三要素檢查表

常見陷阱與優化

• 棧溢出：n 過大導致遞歸深度超限（通常 ~10^5 幀），改用迭代或尾遞歸優化
• 整數溢出：13! 超過 32 位有符號整數範圍，用 long long 或大數庫
• 尾遞歸優化：GCC `-O2` 可優化尾調用，但 C 標準不保證
• 迭代版本：性能更優、無棧風險

  long long fact_iter(int n) {
      long long r = 1;
      for (int i = 2; i <= n; i++) r *= i;
      return r;
  }
  

延伸練習

1. 斐波那契數列遞歸 vs 迭代 vs 矩陣快速冪
2. 漢諾塔遞歸移動步驟打印
3. 二叉樹前/中/後序遍歷遞歸實現