C 語言遞歸精解：字符串反轉輸出的調用棧機制

代碼回顧

void f(char *s) {
    if (!*s) return;   // ① 終止條件
    f(s + 1);          // ② 遞歸調用
    putchar(*s);       // ③ 回溯時輸出
}
int main() {
    f("kernighan");
    putchar('\n');
    return 0;
}

逐步執行流程

1. 遞歸下探：f("kernighan") → f("ernighan") → … → f("n") → f("")。每次調用將指針後移一位，直到遇到 \0 觸發 ① 返回。
2. 回溯輸出：最內層 f("") 直接返回，上一層 f("n") 執行 ③ 輸出 'n'，再返回；依次類推，依次輸出 'a'、'h'、'g'、'i'、'n'、'r'、'e'、'k'。
3. 最終輸出 nahginrek——原字符串的逆序。

關鍵點解析

為什麼不是每層都輸出？

若將 putchar 放在遞歸調用 前，則會正序輸出。當前位置導致輸出動作被壓入調用棧，直到基例返回才開始彈出執行，形成逆序。

遞歸三要素驗證

• 基例：if (!*s) return;
• 縮小問題：s+1 縮短字符串長度
• 合併結果：回溯時輸出當前字符

總結

該函數利用調用棧的後進先出（LIFO）特性，將「輸出」動作延遲到回溯階段，從而以 O(n) 時間、O(n) 棧空間實現字符串反轉。理解遞歸的關鍵在於區分「下探」與「回溯」兩個階段的代碼執行順序。