Java 遞歸求和的兩種經典寫法與非遞歸替代方案

遞歸求和：從入門到優化

遞歸是解決「問題可分解為同類子問題」的利器。以 1+2+...+n 為例，展示兩種遞歸寫法並分析優缺點，最後給出迭代替代方案。

寫法一：實例變量累加（尾遞歸形式）

public class Student {
    private int sum = 0; // 實例變量保持狀態
    
    public void sum(int num) {
        this.sum += num--;
        if (num > 0) {
            sum(num); // 遞歸調用
        } else {
            System.out.println("sum = " + sum);
        }
    }
}

特點：利用實例字段保存中間結果，邏輯直觀。
缺點：非線程安全、污染對象狀態、非尾調用優化（Java 不保證 TCO），大 n 易棧溢出。

寫法二：純函數式返回值遞歸

public class Test {
    public static int sum(int num) {
        if (num == 1) return 1; // 基準情況
        return num + sum(num - 1); // 遞歸分解
    }
    
    public static void main(String[] args) {
        System.out.println(sum(100)); // 5050
    }
}

優勢：無副作用、可並行、易測試、符合函數式思維。
同樣風險：棧深度受限，n > 10,000 通常拋 StackOverflowError。

非遞歸替代：迭代與數學公式

for 迴圈

public static int sumLoop(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) sum += i;
    return sum;
}

while 迴圈

public static int sumWhile(int n) {
    int sum = 0;
    while (n > 0) sum += n--;
    return sum;
}

高斯公式 O(1)

public static int sumFormula(int n) {
    return n * (n + 1) / 2;
}

效能與選擇指南

遞歸最佳實踐原則

1. 必須有明確基準情況，避免無限遞歸
2. 向基準情況收斂，參數每次必須「變小」
3. 考慮尾遞歸優化（Java 暫不支持，可手動改迭代）
4. 大數據量改用迭代，或引入 Stream API：LongStream.rangeClosed(1, n).sum()

理解遞歸本質，靈活選擇工具，才是工程師的基本功。