C 語言遞歸入門：階乘計算遞歸實現

遞歸核心思想

遞歸是函數直接或間接調用自身的編程技巧。解決問題需具備兩個條件：

1. 基線條件：問題規模縮減到最簡單情況時直接返回結果，停止遞歸；
2. 遞歸步驟：將大規模問題轉化為小一號的同類問題，調用自身求解。

階乘遞歸模型

數學定義：n! = n × (n-1)!，1! = 1（基線條件）。

代碼實現

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

// 遞歸函數：計算 n!
int factorial(int n) {
    if (n == 1) return 1;          // 基線條件
    return n * factorial(n - 1);   // 遞歸步驟
}

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

執行流程圖解 (以 4! 為例)

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

注意事項

• 棧溢出風險：輸入過大導致遞歸深度超過棧限制（通常數萬層）；
• 整型溢出：13! 超過 32 位有符號整數範圍，建議用 long long 或大數庫；
• 尾遞歸優化：現代編譯器可優化尾遞歸，但 C 標準不保證，勿依賴。

遞歸與迭代對比

階乘用迭代（循環）更高效、無棧風險。遞歸適合樹遍歷、分治算法（如快排）、回溯等天生遞歸結構的問題。