C 語言遞歸陷阱：啤酒飲料購買問題的遞歸邏輯錯誤與優化解法

原題

啤酒 2.3 元/罐，飲料 1.9 元/罐，共花 82.3 元，啤酒數量少於飲料，求啤酒罐數。

原代碼缺陷分析

int num_pi=0, num_yin=1, money=823;
int fun(int mon) {
    if (mon > money) return 0;
    if (mon == money && num_pi < num_yin) { printf("%d\n", num_pi); return 0; }
    num_pi++; fun(mon+23);
    num_yin++; fun(mon+19);  // 邏輯錯誤：全局變量共享導致狀態混亂，無回溯機制
}

• 全局變量 num_pi、num_yin 在遞歸分支間相互干擾，無法正確回溯。
• 缺少「撤銷選擇」步驟，導致計數單調遞增，永遠無法滿足 mon == money 並同時符合數量約束。
• 遞歸樹呈指數級增長，極易棧溢出。

正確遞歸思路：參數傳遞狀態 + 剪枝

void solve(int beer, int beverage) {
    int cost = beer * 23 + beverage * 19;
    if (cost > 823) return;                 // 剪枝：超支
    if (cost == 823) {                      // 找到解
        if (beer < beverage) printf("%d %d\n", beer, beverage);
        return;
    }
    solve(beer, beverage + 1);              // 繼續買飲料
    solve(beer + 1, beverage);              // 回溯點：嘗試買啤酒
}

更優解法：雙層循環窮舉（O(n)）

for (int beer = 0; beer <= 823/23; ++beer) {
    int rem = 823 - beer * 23;
    if (rem % 19 == 0) {
        int beverage = rem / 19;
        if (beer < beverage) printf("啤酒:%d 飲料:%d\n", beer, beverage);
    }
}

結論

遞歸需「狀態參數化、回溯恢復、邊界剪枝」；簡單整數規劃問題優先考慮數學推導或迭代窮舉，避免遞歸開銷。