Java 資料結構與演算法：三角數列遞歸實作

什麼是三角數？

三角數序列為：1, 3, 6, 10, 15, 21... 第 n 項代表可排成等邊三角形的點數。其數學定義為：

T(1) = 1
T(n) = n + T(n-1) (n > 1)

這與高斯求和 1 到 100 的邏輯相同，本質是等差數列求和，閉合公式為 n(n+1)/2。

遞歸實作

package datastructure;

public class TriangleNumber {
    public static void main(String[] args) {
        TriangleNumber tn = new TriangleNumber();
        int n = 100;
        System.out.println("第 " + n + " 項三角數：" + tn.getValue(n));
        // 驗證閉合公式
        System.out.println("公式驗證：" + (n * (n + 1) / 2));
    }

    /**
     * 遞歸計算第 n 項三角數
     * @param n 項數 (n >= 1)
     * @return 三角數值
     */
    public int getValue(int n) {
        if (n == 1) {
            return 1;
        }
        return n + getValue(n - 1);
    }
}

效能考量

• 遞歸版本時間複雜度 O(n)，空間複雜度 O(n)（呼叫堆疊）。
• 大數值（如 n > 10000）易導致 StackOverflowError。
• 生產環境建議使用閉合公式 n*(n+1)/2 或迭代累加，時間 O(1) 或 O(n)、空間 O(1)。

延伸思考

三角數是多邊形數的一種。同理可推導四邊形數（平方數）、五邊形數等，公式皆為二次多項式，展現數學規律在程式設計中的優美對應。