C語言遞歸入門：階乘函數的遞歸實現與執行流程分析

C語言遞歸入門：階乘函數的遞歸實現與執行流程分析

遞歸三要素：基線條件（終止條件）、遞歸調用（縮小問題規模）、結果合併。

階乘遞歸定義

n! = n × (n-1)! ，0! = 1

代碼實現

#include <stdio.h>
#include <stdlib.h>

int factorial(int n) {
    if (n == 1) return 1;          // 基線條件
    return n * factorial(n - 1);   // 遞歸調用 + 合併
}

int main() {
    int n;
    printf("請輸入正整數：");
    scanf("%d", &n);
    printf("%d! = %d\n", n, factorial(n));
    system("pause");
    return 0;
}

執行流程圖解（以 4! 為例）

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

遞歸 vs 迴圈

尾遞歸優化

若編譯器支援尾呼叫優化（-O2），將遞歸改寫為累加器形式可避免棧溢出：

int fact_tail(int n, int acc) {
    if (n == 1) return acc;
    return fact_tail(n - 1, n * acc);
}
// 調用：fact_tail(n, 1)