C 語言遞歸實戰：空瓶換汽水問題的遞歸解法

問題描述

汽水 1 元/瓶，2 個空瓶可換 1 瓶。手持 20 元，最多能喝多少瓶？

遞歸建模

設 exchange(bottles) 返回由 bottles 個空瓶繼續換酒能喝的額外瓶數。每次換酒消耗 2 空瓶得 1 滿瓶，喝完又得 1 空瓶，故空瓶淨減 1。遞歸關係：

exchange(b) = 0                     (b < 2)
exchange(b) = 1 + exchange(b - 1)   (b >= 2)

C 代碼實現

#include <stdio.h>

int exchange(int bottles) {
    if (bottles < 2) return 0;
    return 1 + exchange(bottles - 1);
}

int main() {
    int money = 20;
    int total = money + exchange(money);  // 初始滿瓶 + 兌換所得
    printf("最多能喝 %d 瓶\n", total);
    return 0;
}

運行結果

輸出：最多能喝 39 瓶。

遞歸深度與優化

最大深度 O(n)，對於 n=1e9 會棧溢出。可改寫尾遞歸或迭代：

int exchange_iter(int b) {
    int extra = 0;
    while (b >= 2) { b -= 1; extra++; }  // 每次淨減 1
    return extra;
}

總結

空瓶換酒是線性遞歸的經典例題。理解「淨減 1」的不變量，即可輕松寫出遞歸與迭代兩種形式。實際工程中優先考慮迭代避免棧溢出。