C 語言經典遞歸/迭代題：猴子吃桃問題

問題

猴子摘桃若干。第 1 天吃一半多 1 個，第 2 天吃剩餘一半多 1 個……第 10 天早上剩 1 個。求初始桃數。

逆向思維（遞推公式）

設第 i 天早上剩 x_i 個。
第 i-1 天剩 x_{i-1}，吃掉 x_{i-1}/2 + 1，剩 x_i = x_{i-1} - (x_{i-1}/2 + 1) = x_{i-1}/2 - 1。
解得逆推公式：x_{i-1} = 2*(x_i + 1)。

代碼實現（迭代版）

#include <stdio.h>

int main() {
    int days, peach = 1; // 第 10 天早上剩 1 個
    printf("請輸入天數: ");
    scanf("%d", &days);
    for (int i = 1; i < days; ++i) {
        peach = 2 * (peach + 1);
    }
    printf("第一天共摘 %d 個桃子\n", peach);
    return 0;
}

運行示例

請輸入天數: 10
第一天共摘 1534 個桃子

遞歸版（教學）

int peachRec(int day, int current) {
    if (day == 1) return current;
    return peachRec(day - 1, 2 * (current + 1));
}
// 調用：peachRec(10, 1)

數學通項

x_1 = 2^{n-1} * (x_n + 2) - 2。
n=10, x_10=1 → x_1 = 2^9 * 3 - 2 = 1534。