C語言遞歸經典練習：砲彈金字塔、冪運算與最大公約數

練習一：砲彈金字塔總數

第 h 層有 h² 個砲彈，遞歸關係：CannonBall(h) = CannonBall(h-1) + h²，基線 h=1 返回 1。

int CannonBall(int h) {
    if (h == 1) return 1;
    return CannonBall(h-1) + h*h; // pow(h,2) 改為整數乘法更高效
}
int main(void) {
    printf("%d\n", CannonBall(4)); // 輸出 30
    return 0;
}

練習二：遞歸實現冪運算 nk

遞歸定義：nk = n × nk-1，基線 k=0 返回 1。

int RaiseToPower(int n, int k) {
    if (k == 0) return 1;
    return n * RaiseToPower(n, k-1);
}
int main() {
    printf("%d\n", RaiseToPower(3,4)); // 輸出 81
    return 0;
}

練習三：輾轉相除法求最大公約數

歐幾里得算法：gcd(m,n) = gcd(n, m%n)，直到餘數為 0。

int gcd(int m, int n) {
    if (m % n == 0) return n;
    return gcd(n, m % n);
}
int main() {
    printf("%d\n", gcd(18,4)); // 輸出 2
    return 0;
}

遞歸設計核心原則

1. 基線條件：必須有明確終止條件，防止無限遞歸棧溢出。
2. 問題分解：將大問題化為同結構的小問題。
3. 狀態傳遞：通過參數傳遞必要狀態，避免全局變量。

這三道題涵蓋「累加型」「乘積型」「狀態轉移型」遞歸模式，是掌握遞歸思維的絕佳入門素材。