C 語言遞迴演算法解猴子摘桃問題：從終態反推初始值

C 語言遞迴演算法解猴子摘桃問題：從終態反推初始值

遞迴關係

f(10) = 1
f(day) = 2 * (f(day+1) + 1) for day = 9..1

遞迴函數實作

#include <stdio.h>

int peaches(int day) {
    if (day == 10) return 1; // 基礎情況
    return 2 * (peaches(day + 1) + 1); // 遞迴步驟
}

int main() {
    printf("第一天摘了 %d 個桃子\n", peaches(1));
    return 0;
}

遞迴展開圖解

peaches(1)
= 2*(peaches(2)+1)
= 2*(2*(peaches(3)+1)+1)
...
= 2*(2*(...2*(1+1)+1...)+1)  // 9 層
= 1534

迭代版本對比

int peaches_iter() {
    int p = 1;
    for (int d = 9; d >= 1; --d) p = 2*(p+1);
    return p;
}

遞迴版本優雅展示數學定義，迭代版本效能最佳。理解兩者轉換是演算法基本功。