您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 遞歸經典：猴子吃桃問題逆向推導

編輯：Java 相關知識

問題描述

猴子第一天摘若干桃子，吃掉一半再多吃 1 個。第二天對剩餘同樣操作... 第 10 天早上只剩 1 個。求第一天摘了多少？

逆向思維建模

設第 n 天早上剩 f(n) 個：

f(10) = 1
f(n) = (f(n+1) + 1) * 2   // 逆向：前一天剩余 = (今天剩余 + 1) * 2

f(9) = (1+1)*2 = 4
f(8) = (4+1)*2 = 10
f(7) = 22
f(6) = 46
f(5) = 94
f(4) = 190
f(3) = 382
f(2) = 766
f(1) = 1534

Java 遞歸實現

public class MonkeyPeach {
    // 遞歸函數：計算第 day 天早上剩餘桃子數
    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
    }
}

遞歸 vs 迭代對比

// 迭代版 (更高效，無棧溢出風險)
int totalIterative() {
    int peaches = 1;  // 第 10 天
    for (int day = 9; day >= 1; day--) {
        peaches = (peaches + 1) * 2;
    }
    return peaches;  // 1534
}

// 閉式公式 (觀察規律)
// f(n) = 2^(10-n+1) * (1 + 1/2 + 1/4 + ... + 1/2^(10-n)) - 1
// 可用等比數列求和推導，但迭代已足夠簡單

遞歸三要素驗證

現代 Java 增強

import java.util.function.IntUnaryOperator;

public class MonkeyPeachFunctional {
    public static void main(String[] args) {
        // 遞歸函數式寫法 (需配合 Y-Combinator 或遞歸引用)
        IntUnaryOperator total = new IntUnaryOperator() {
            @Override public int applyAsInt(int day) {
                return day == 10 ? 1 : (applyAsInt(day + 1) + 1) * 2;
            }
        };
        System.out.println(total.applyAsInt(1));
        
        // 或使用 Stream 迭代 (非遞歸)
        int result = java.util.stream.IntStream.iterate(1, n -> (n + 1) * 2)
            .limit(9)  // 從第9天倒推到第1天，共9步
            .reduce((a, b) -> b)  // 取最後一個
            .orElse(1);
        System.out.println(result);
    }
}