C 語言遞歸經典案例：五人年齡遞推求解

問題描述

五人同坐，第五人比第四人大 2 歲，第四人比第三人大 2 歲，第三人比第二人大 2 歲，第二人比第一人大 2 歲，第一人 10 歲。求第五人年齡。

遞歸模型建立

設 age(n) 為第 n 人年齡，則：

• 基例：age(1) = 10
• 遞推關係：age(n) = age(n-1) + 2（n > 1）

目標求 age(5)。

代碼實現

#include <stdio.h>

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

int main() {
    printf("his age is :%d\n", age(5));
    return 0;
}

遞歸執行過程圖解

調用棧（遞推階段）：
age(5) → age(4) → age(3) → age(2) → age(1) 返回 10

返回棧（回推階段）：
age(2) = 10 + 2 = 12
age(3) = 12 + 2 = 14
age(4) = 14 + 2 = 16
age(5) = 16 + 2 = 18

輸出結果

his age is :18

遞歸 vs 迭代對比

迭代版實現

int age_iter(int n) {
    int a = 10;
    for (int i = 2; i <= n; i++)
        a += 2;
    return a;
}

遞歸優化：尾遞歸

將加法操作前移，使遞歸調用成為函數最後一條指令：

int age_tail(int n, int acc) {
    if (n == 1) return acc;
    return age_tail(n - 1, acc + 2);
}
// 調用：age_tail(5, 10)

支持尾調用優化（TCO）的編譯器（GCC -O2/-O3、Clang、MSVC）可將其轉為迭代機器碼，消除棧增長。

適用場景建議

• 教學演示、數學歸納定義、樹/圖遍歷 → 首選遞歸
• 線性遞推、高性能要求、嵌入式受限環境 → 首選迭代或尾遞歸