C語言遞歸實戰：從數字累加到素數求和的完整指南

遞歸算法的核心思想與實戰演練

遞歸是程式設計中極具優雅性的技術，它允許函數直接或間接地調用自身，將複雜問題分解為相似的子問題。本文通過兩個經典案例——數字累加與素數累加，深入剖析遞歸的實現機制、邊界條件設計以及潛在風險。

案例一：數字累加（1 到 n 求和）

最基礎的遞歸範例是計算 1 到 n 的整數和。關鍵在於確立「基準情況」與「遞歸步驟」：

• 基準情況：當 n ≤ 0 返回 0，n = 1 返回 1。
• 遞歸步驟：返回 n + sum(n-1)，將問題規模逐步縮小。

int sum(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return n + sum(n - 1);
}

執行流程以 sum(3) 為例：sum(3) → 3 + sum(2) → 3 + (2 + sum(1)) → 3 + 2 + 1 = 6。每層調用都在堆疊中保留狀態，最終回溯求值。

案例二：素數累加（1 到 n 內所有素數之和）

此案例結合了「素數判斷」與「遞歸累加」，展示如何將輔助函數整合進遞歸主流程：

// 判斷素數：是則返回自身，否則返回 0
int judge(int n) {
    for (int i = 2; i < n/2 + 1; ++i)
        if (n % i == 0) return 0;
    return n;
}

// 遞歸累加素數
int sumOfPrime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 2;
    return judge(n) + sumOfPrime(n - 1);
}

以 sumOfPrime(10) 為例，程式會依次判斷 10、9、8…2 的素數性，累加 2+3+5+7 = 17。注意 judge 函數的優化空間：試除上限可縮減至 √n，並跳過偶數檢查。

遞歸的雙刃劍：優勢與風險並存

優勢：對於漢諾塔、二分查找、快速排序、斐波那契數列等固有遞歸結構的問題，遞歸代碼極度簡潔、易理解。

風險：

1. 棧溢位：若無正確出口或深度過大，會耗盡棧空間。Windows 下表現為程式假死，Linux 內核檢測到內存耗盡甚至會觸發系統重啟——這正是某些 Android 病毒利用遞歸導致手機重啟的原理。
2. 效率開銷：函數調用開銷大，重複計算嚴重（如朴素遞歸斐波那契）。
3. 可讀性陷阱：過度複雜的遞歸邏輯反而難以維護。

最佳實踐建議

• 永遠優先設計清晰的基準情況，確保遞歸收斂。
• 評估最大遞歸深度，必要時改用迭代或尾遞歸優化（詳見《尾遞歸=遞歸+迭代？》一文）。
• 對重複子問題應用備忘錄或動態規劃優化。
• 在系統級/嵌入式開發中謹慎使用深度遞歸，考慮棧大小限制。

遞歸是把雙刃劍：用得好能化繁為簡，用不好則引發災難性後果。掌握其本質，方能駕馭其威力。