C 語言遞迴入門：陣列求和與求積的遞迴實作 (附迭代對比)

前言：遞迴 — 解決問題的「自我相似」思維

遞迴是將問題分解為**相同性質的較小子問題**，直到達到**基底情況** 直接求解。對於陣列求和、求積等線性結構問題，遞迴提供了極簡潔的表達，但需注意效能與堆疊深度。

遞迴版本：求和與求積

#include 
#include 

#define N 10

// 遞迴求和: sum(arr, n) = arr[n-1] + sum(arr, n-1)
float recursive_sum(float arr[], int n) {
    if (n <= 0) return 0;           // 基底情況: 空陣列和為 0
    return arr[n-1] + recursive_sum(arr, n-1);
}

// 遞迴求積: prod(arr, n) = arr[n-1] * prod(arr, n-1)
float recursive_prod(float arr[], int n) {
    if (n <= 0) return 1;           // 基底情況: 空陣列積為 1 (乘法單位元)
    return arr[n-1] * recursive_prod(arr, n-1);
}

int main() {
    float arr[N];
    printf("輸入 %d 個浮點數:\n", N);
    for (int i = 0; i < N; i++) {
        printf("arr[%d] = ", i);
        if (scanf("%f", &arr[i]) != 1) return 1;
    }

    float sum = recursive_sum(arr, N);
    float prod = recursive_prod(arr, N);

    printf("和 = %.2f, 平均 = %.2f\n", sum, sum/N);
    printf("積 = %.2f, 幾何平均 = %.2f\n", prod, powf(prod, 1.0f/N));

    return 0;
}

遞迴執行流程圖解 (以求和為例)

recursive_sum(arr, 4)
  │ arr = [1,2,3,4]
  ├─► return arr[3] + recursive_sum(arr, 3)
  │       │
  │       ├─► return arr[2] + recursive_sum(arr, 2)
  │       │       │
  │       │       ├─► return arr[1] + recursive_sum(arr, 1)
  │       │       │       │
  │       │       │       ├─► return arr[0] + recursive_sum(arr, 0)
  │       │       │       │       │
  │       │       │       │       └─► return 0 (基底)
  │       │       │       │
  │       │       │       └─► 1 + 0 = 1
  │       │       │
  │       │       └─► 2 + 1 = 3
  │       │
  │       └─► 3 + 3 = 6
  │
  └─► 4 + 6 = 10

關鍵點：為什麼需要兩個陣列副本？

原文提到：「一定要用兩個數組，因為數組做參數，不是傳值調用」。

澄清：C 語言陣列參數**退化為指標**，函式內修改陣列元素**會影響原陣列**。若遞迴過程中修改陣列 (如將已處理元素歸零/歸一)，原陣列會被破壞，導致後續計算錯誤。

// 原文做法: 修改陣列元素作為「標記已處理」
float destructive_sum(float arr[], int n) {
    if (n == 1) return arr[0];
    float val = arr[n-1];
    arr[n-1] = 0;  // 破壞原陣列！
    return val + destructive_sum(arr, n-1);
}

// ✅ 正確做法: 不修改陣列，純靠索引/指標推進
float safe_sum(const float arr[], int n) {  // const 保護
    if (n <= 0) return 0;
    return arr[n-1] + safe_sum(arr, n-1);
}

迭代版本對比：效能與堆疊安全

float iterative_sum(const float arr[], int n) {
    float sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}

float iterative_prod(const float arr[], int n) {
    float prod = 1;
    for (int i = 0; i < n; i++) prod *= arr[i];
    return prod;
}

遞迴 vs 迭代 完整對比

尾端遞迴最佳化 (TCO) 示範

// 尾端遞迴: 遞迴呼叫是最後一步運算
float tail_sum(const float arr[], int n, float acc) {
    if (n <= 0) return acc;
    return tail_sum(arr, n-1, acc + arr[n-1]);  // 尾端呼叫
}
// 呼叫: tail_sum(arr, N, 0);
// GCC/Clang -O2 會優化為迴圈，無堆疊增長

進階：分治法求和 (平衡遞迴，深度 log n)

float divide_sum(const float arr[], int left, int right) {  // [left, right)
    if (left >= right) return 0;
    if (left + 1 == right) return arr[left];
    int mid = left + (right - left) / 2;
    return divide_sum(arr, left, mid) + divide_sum(arr, mid, right);
}
// 呼叫: divide_sum(arr, 0, N);
// 遞迴深度: log2(N) ≈ 14 (N=10000)，極大降低堆疊風險

總結與建議

1. 學習遞迴：理解基底情況、遞迴步驟、問題分解 — 程式設計核心思維。
2. 生產代碼：線性陣列處理**優先用迭代** (或標準庫 std::accumulate C++)，避免堆疊溢位與呼叫開銷。
3. 必須遞迴時：
   • 加上 const 保護參數
   • 考慮尾端遞迴 + 編譯器最佳化
   • 大規模資料改用分治法 (深度 log n)
   • 設定堆疊大小 (嵌入式/執行緒) 或改用手動堆疊模擬
4. 除錯技巧：用 gdb bt 檢視遞迴堆疊、valgrind --tool=callgrind 分析呼叫開銷。

遞迴是把雙面刃：用得好極其優雅，用不好隱患重重。掌握其本質與代價，才能在正確場合發揮最大價值。