遞迴求解年齡問題：數學歸納法在程式設計中的應用

問題描述

5 人同桌，第 5 人比第 4 人大 2 歲，第 4 人比第 3 人大 2 歲……第 1 人 10 歲。求第 5 人年齡。

遞迴模型

age(n) = 10                 , n = 1
age(n) = age(n-1) + 2       , n > 1

程式碼實作

#include <stdio.h>

int age(int n) {
    if (n == 1) return 10;
    return age(n - 1) + 2;
}

int main(void) {
    printf("第 5 人年齡：%d 歲\n", age(5));  // 輸出 18
    return 0;
}

遞迴 vs 迭代

圖示說明

延伸思考

• 尾端遞迴優化（TCO）可消除堆疊增長
• 大數值遞迴需改用迭代或動態規劃避免堆疊溢位
• 費波那契數列、漢諾塔等經典遞迴問題同理