Java 經典遞歸練習：猴子吃桃問題

問題描述

猴子第一天摘若干桃子，吃掉一半再多吃一個。第二天同樣吃掉剩餘的一半再多一個。如此重複，到第 10 天早上只剩 1 個桃子。求第一天摘了多少個。

逆向思維分析

第 10 天剩 1 個 → 第 9 天結束時剩 (1+1)*2 = 4 → 第 8 天結束時 (4+1)*2 = 10 ... 遞推公式：f(day) = (f(day+1) + 1) * 2，基例 f(10) = 1。

遞歸實現

public class MonkeyPeach {
    static int total(int day) {
        if (day == 10) return 1;
        return (total(day + 1) + 1) * 2;
    }
    public static void main(String[] args) {
        System.out.println("第一天共摘了 " + total(1) + " 個桃子"); // 1534
    }
}

迭代版本（避免棧溢出）

int peach = 1;
for (int day = 9; day >= 1; day--) {
    peach = (peach + 1) * 2;
}
System.out.println(peach); // 1534

舉一反三

• 天數、剩餘數、吃法比例可參數化
• 本質是**線性遞推**，時間 O(n)，空間遞歸 O(n) / 迭代 O(1)