遞歸反轉字串是理解**遞歸調用棧**、**函數調用約定**、**指標算術**的絕佳案例。本文提供標準遞歸實現、棧幀演進圖解、迭代版對比、尾遞歸優化分析。
#include#include void reverse_string(const char *str) { if (*str == '\0') return; // 基準情況：空串 reverse_string(str + 1); // 遞歸處理剩餘子串 putchar(*str); // 回溯時輸出當前字元 } int main() { char *s = "abcdefghijk"; reverse_string(s); putchar('\n'); return 0; }
kjihgfedcba
reverse_string("abc")
│
├─ reverse_string("bc") // str 指向 'b'
│ │
│ ├─ reverse_string("c") // str 指向 'c'
│ │ │
│ │ ├─ reverse_string("") // str 指向 '\0'，基準情況返回
│ │ │
│ │ └─ putchar('c') // 輸出 'c'
│ │
│ └─ putchar('b') // 輸出 'b'
│
└─ putchar('a') // 輸出 'a'
最終輸出: "cba"
棧增長方向 (高位址 → 低位址) +------------------------+ | 主調函數棧幀 | +------------------------+ | 返回位址 | | 保存的基址指標 (rbp) | | 參數 str (指標, 8B) | ← 每層不同：指向 "abc", "bc", "c", "" | 區域變數 (無) | +------------------------+ | ... 遞歸深度 n 層 ... | +------------------------+
void reverse_iterative(char *str) {
if (!str) return;
char *end = str + strlen(str) - 1;
while (str < end) {
char tmp = *str;
*str++ = *end;
*end-- = tmp;
}
}
// 或標準庫
void reverse_stdlib(char *str) {
// C++: std::reverse(str, str+strlen(str));
// C: 無標準原地反轉，需手寫或用 strrev (非標準)
}
// 當前版本：非尾遞歸
void reverse_string(str) {
if (!*str) return;
reverse_string(str+1); // 遞歸調用非最後操作
putchar(*str); // 返回後還有操作 → 無法 TCO
}
// 尾遞歸版 (需額外參數累積結果)
void reverse_tail(const char *str, char *out, int *idx) {
if (!*str) { out[*idx] = '\0'; return; }
reverse_tail(str+1, out, idx);
out[(*idx)++] = *str; // 仍在返回後操作，非尾調用
}
// 真正尾遞歸需改為累積器傳遞 (C 編譯器對 TCO 支援有限)
**結論**：字串反轉**天然非尾遞歸**，因輸出順序與遞歸深度相反。GCC/Clang `-O2/-O3` 對簡單尾遞歸可優化，但此模式無法優化，**迭代版唯一正解**。
| 錯誤 | 後果 | 修正 |
|---|---|---|
| 基準情況寫錯 (`*str` 而非 `*str=='\0'`) | 提前結束或無限遞歸 | `if (!*str) return;` |
| 指標算術錯 (`str++` 修改原指標) | 上層指標污染 | 傳 `str+1` 不修改原值 |
| 超長字串導致棧溢出 | Stack Overflow 崩潰 | 改用迭代版 |
| 字串常量傳入原地反轉函數 | UB (段錯誤) | 只讀字串用遞歸輸出或複製後反轉 |
遞歸反轉字串**教學價值極高、生產價值為零**。核心收穫：理解**調用棧 LIFO 特性實現順序反轉**、指標算術不修改原值、基準情況終止條件、棧溢出風險。生產代碼**強制使用雙指針迭代原地交換**，O(1) 空間、無棧溢出、編譯器可向量化。面試必會：遞歸棧幀圖解、尾遞歸判斷、迭代版雙指針寫法、字串常量不可修改鐵律。
