递归与字符串：字符串反转的递归实现

字符串反转，这大概是每个程序员都写过的代码。用循环写，三五行就搞定。但今天我想聊聊递归版本——不是为了炫技，而是因为递归处理字符串的方式，能帮你打开一扇新的门。

我刚开始学递归时，总觉得这东西绕。明明循环能解决的问题，干嘛要递归？直到有一次我在项目中处理一个深层嵌套的JSON字符串解析，才发现递归的优雅之处。嗯，咱们今天就拿字符串反转这个经典例子，把递归的思路彻底讲透。

递归反转的核心思路

先想想看，字符串反转到底在做什么？

比如 "hello" 反转成 "olleh"。你仔细看这个过程：

• 把第一个字符 'h' 放到最后
• 把剩下的 "ello" 反转
• 再把 'e' 放到最后
• 把剩下的 "llo" 反转
• ……

发现了没？这就是一个典型的递归结构：每次处理一个字符，剩下的交给递归。

说白了，递归就是把一个大问题拆成「一小步 + 一个规模更小的同类问题」。你只需要关心这一小步怎么做，剩下的递归会帮你搞定。

代码实现：从理论到实战

先看一个最直观的递归实现：

#include <stdio.h>
#include <string.h>

// 递归反转字符串，返回反转后的新字符串
void reverse_string(char *str, int start, int end) {
    // 递归终止条件：只剩一个字符或空串
    if (start >= end) {
        return;
    }
    
    // 交换首尾字符
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;
    
    // 递归处理剩余部分
    reverse_string(str, start + 1, end - 1);
}

int main() {
    char str[] = "hello";
    printf("原字符串: %s\n", str);
    
    reverse_string(str, 0, strlen(str) - 1);
    
    printf("反转后: %s\n", str);
    return 0;
}

这段代码我解释一下：

• 终止条件：start >= end，说明已经处理完了所有字符
• 当前步骤：交换 str[start] 和 str[end]
• 递归调用：处理 start+1 到 end-1 的子串

运行过程是这样的：

原始: h e l l o
第1步: 交换 h 和 o → o e l l h
第2步: 交换 e 和 l → o l l e h
第3步: start=2, end=2, 终止
结果: o l l e h

我个人习惯用这种双指针的方式写递归反转。为什么？因为它在原字符串上操作，不需要额外分配内存，效率高。

另一种写法：返回新字符串

有时候你不想修改原字符串，而是想返回一个新的反转字符串。那可以这样写：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 递归反转，返回新字符串
char* reverse_string_new(const char *str) {
    int len = strlen(str);
    
    // 终止条件：空串或单字符
    if (len <= 1) {
        char *result = (char*)malloc(len + 1);
        strcpy(result, str);
        return result;
    }
    
    // 递归反转子串 str[1:]
    char *sub_reversed = reverse_string_new(str + 1);
    
    // 计算新字符串长度
    int sub_len = strlen(sub_reversed);
    char *result = (char*)malloc(len + 1);
    
    // 将子串的反转结果放到前面
    strcpy(result, sub_reversed);
    // 将原首字符放到最后
    result[sub_len] = str[0];
    result[len] = '\0';
    
    free(sub_reversed);
    return result;
}

int main() {
    const char *str = "hello";
    char *reversed = reverse_string_new(str);
    printf("原字符串: %s\n", str);
    printf("反转后: %s\n", reversed);
    free(reversed);
    return 0;
}

递归的调用栈分析

理解递归，关键要理解调用栈。我画了一张图，帮你直观地看明白：

从这张图可以看得很清楚：递归先一路深入到最底层，然后逐层返回。每一层只做一件事——交换两个字符。这就是递归的「分而治之」思想。

避坑指南：递归的陷阱

我在项目中用递归反转字符串时，踩过几个坑，分享给你：

递归 vs 循环：怎么选？

说实话，字符串反转这个场景，循环比递归更实用。但为什么还要学递归？因为递归的思想可以迁移到更复杂的问题上，比如：

• 反转链表（递归写法比循环优雅得多）
• 解析嵌套的括号表达式
• 遍历文件目录树
• 处理JSON/XML等嵌套数据结构

你想想看，这些场景如果用循环写，你得手动维护一个栈。而递归天然就自带调用栈，写起来思路更清晰。

所以我的建议是：简单问题用循环，复杂嵌套问题用递归。别为了用递归而用递归，也别因为觉得递归难就完全不用。工具嘛，多一把在手，总没坏处。

好了，字符串反转的递归实现就讲到这里。代码不多，但背后的递归思想值得好好消化。下次遇到类似的问题，不妨先想想：能不能拆成「一小步 + 一个更小的问题」？如果能，递归可能就是你的好帮手。

---

公众号:蓝海资料掘金营，微信deep3321