遞迴練習：計算 a 到 b 的整數和（C/C++ 實作）

遞迴演算法練習：計算區間 [a, b] 所有整數之和

經典遞迴入門題目：給定兩個整數 a 和 b（a ≤ b），使用遞迴計算從 a 到 b（含）所有整數的和。

遞迴思路

• 基本情況：若 a > b，區間為空，回傳 0
• 遞迴關係：sum(a, b) = a + sum(a+1, b)

完整程式碼

/*********************************************************************************
 * 遞迴練習：a 到 b 的整數和
 *********************************************************************************/
#include <iostream>
using namespace std;

static int sumRange(int a, int b);

int main() {
    cout << "sum(1, 4) = " << sumRange(1, 4) << endl;  // 1+2+3+4=10
    return 0;
}

static int sumRange(int a, int b) {
    if (a > b) 
        return 0;                    // 基本情況：區間無效
    return a + sumRange(a + 1, b);   // 遞迴分解：當前值 + 剩餘區間和
}

執行追蹤（sumRange(1, 4)）

sumRange(1, 4)
= 1 + sumRange(2, 4)
= 1 + (2 + sumRange(3, 4))
= 1 + 2 + (3 + sumRange(4, 4))
= 1 + 2 + 3 + (4 + sumRange(5, 4))
= 1 + 2 + 3 + 4 + 0
= 10

關鍵點總結

• 遞迴必須有明確的終止條件（此處為 a > b）
• 每次遞迴呼叫都要讓問題規模縮小（a+1 逼近 b）
• 此題也可用等差數列公式 (a+b)*(b-a+1)/2 O(1) 解決，遞迴主要用於練習思維
• 注意：大區間可能導致棧溢位，實際工程中大迴圈優先考慮迭代或數學公式

延伸練習

1. 修改為計算 a 到 b 之間所有偶數之和
2. 實作遞迴版 factorial(n) 階乘函數
3. 嘗試尾遞迴優化版本（需編譯器支援）