C 語言遞歸實現字符串逆序：reverse_string 經典教學版

C 語言遞歸實現字符串逆序：reverse_string 經典教學版

遞歸實現字符串原地逆序：將首尾字符交換，中間子串遞歸逆序。要求不使用庫函數、不申請臨時數組。

一、 遞歸邏輯

1. 計算字符串長度 len。
2. 若 len <= 1 直接返回（基線條件）。
3. 交換 str[0] 與 str[len-1]。
4. 將 str[len-1] 暫存為 \0，遞歸處理 str+1（長度 len-2）。
5. 遞歸返回後恢復 str[len-1] 為暫存字符。

二、 代碼實現

#include <stdio.h>
#include <assert.h>

int my_strlen(const char *s) {
    int len = 0; while (*s++) len++; return len;
}

void reverse_string(char *str) {
    assert(str);
    int len = my_strlen(str);
    if (len > 0) {
        char tmp = str[0];
        str[0] = str[len-1];
        str[len-1] = '\0';           // 截斷尾部，構造子問題
        reverse_string(str + 1);     // 遞歸處理中間子串
        str[len-1] = tmp;            // 恢復尾部字符
    }
}

int main() {
    char arr[] = "abcdef";
    reverse_string(arr);
    printf("%s\n", arr); // fedcba
    return 0;
}

三、 關鍵點解析

• 構造子問題：將尾字符暫存為 \0，使 str+1 指向的子串長度減 2，遞歸終止條件自然滿足。
• 恢復現場：遞歸返回後必須恢復 str[len-1]，否則尾字符丟失。
• 棧深度：len/2 層，長字符串可能棧溢出，教學適用，生產慎用。

四、 迭代版對比

void reverse_iter(char *str) {
    char *l = str, *r = str + strlen(str) - 1;
    while (l < r) { char t = *l; *l++ = *r; *r-- = t; }
}

迭代版 O(1) 空間、無棧溢出風險、效率更高，工程首選。

五、 總結

遞歸逆序展示「分治」思想：大問題分解為首尾交換 + 子問題逆序。理解遞歸基線條件、狀態保存/恢復、棧帧變化，是掌握遞歸編程的關鍵。