C/C++ 遞歸思想、實現與遞歸轉循環完全指南

遞歸是「自己調用自己」解決問題，核心要素：遞歸體（如何分解）+ 終止條件（何時停止）。

經典例 1：斐波那契數列

int Fib(int n) {
    if (n < 3) return 1;
    return Fib(n-1) + Fib(n-2); // 指數級調用，極其低效
}

Fib(20) 調用超 1 萬次，棧溢出風險大。

循環版（O(n) 時間，O(1) 空間）

int Fib(int n) {
    int a[3] = {1,1,1};
    for (int i = 3; i <= n; i++)
        a[i%3] = a[(i+1)%3] + a[(i+2)%3];
    return a[n%3];
}

例 2：1 加到 100

遞歸寫法（教學用，不推薦生產）：

int sum = 0;
int Acc(int i) {
    if (i == 0) return 0;
    return sum += Acc(i-1) + 1;
}

例 3：母牛生育問題

規律：f(n) = f(n-1) + f(n-3)（第 n 年新增牛 = 3 年前存活牛數）。

int Cattle(int n) {
    if (n < 4) return 1;
    return Cattle(n-1) + Cattle(n-3);
}

同樣存在指數級重複計算，循環/備忘錄優化極易實現。

遞歸轉循環通用技巧

1. 尾遞歸：最後一步是遞歸調用，直接改 while 循環，參數變局部變量；
2. 備忘錄 / DP：數組緩存子問題結果，自底向上填表；
3. 模擬棧：通用但繁瑣，手動維護調用幀。

遞歸 vs 循環

建議

• 優先考慮循環/DP 解決線性遞歸問題；
• 樹圖結構、分治算法（快排、歸併）、回溯搜索，遞歸更自然；
• 遞歸深度超過 ~10^5 時必須轉循環或增大棧。