题目

用递归反转字符串

思路

本题用递归反转字符串（原地交换）。

函数 reverse(s, l, r)：若 l>=r 结束；否则交换 s[l] 与 s[r]，再递归处理中间区间 l+1, r-1。主程序对整串调用 reverse(s, 0, len-1)。

解题分析

递归交换首尾再处理中间子串。迭代双指针与第 50 题相同。递归深度约 n/2，字符串很长时迭代更安全。

完整程序

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

static void rev(char *s, int i, int j)
{
    if (i >= j) {
        return;
    }
    char t = s[i];
    s[i] = s[j];
    s[j] = t;
    rev(s, i + 1, j - 1);
}

int main(void)
{
    char s[500];
    if (scanf("%499s", s) != 1) {
        return 1;
    }
    rev(s, 0, (int)strlen(s) - 1);
    printf("%s\n", s);
    return 0;
}

运行示例

输入：

abcd

输出：

dcba