21、递归与字符串：判断回文字符串的递归实现

回文字符串，说白了就是正着读和反着读都一样的字符串。比如 "aba"、"level"、"上海自来水来自海上" 都是回文。判断回文的方法很多，但用递归来实现，我个人觉得是最优雅的一种方式。

我记得刚入行那会儿，第一次看到递归判断回文的代码，心里想的是：「这代码也太短了吧？」后来自己动手写了几遍，才真正体会到递归的妙处——它把「比较首尾字符」这个动作，一层层地拆解下去，直到字符串被「剥」完。

回文判断的核心思路

判断一个字符串是不是回文，其实就三步：

1. 看首尾：比较第一个字符和最后一个字符是否相等
2. 往里缩：如果相等，去掉首尾，看剩下的子串
3. 重复：直到只剩 0 个或 1 个字符，那肯定是回文

你想想看，这个过程天然就是递归的。每次处理一个更小的子问题，直到遇到「基准情况」——也就是空串或单字符。

递归函数的三个要素

写递归函数，我习惯先想清楚三件事：

要素	说明	回文例子
基准情况	什么时候直接返回，不再递归	字符串长度 ≤ 1，返回 true
递归调用	如何缩小问题规模	去掉首尾字符，判断子串
返回值	如何组合子问题的结果	首尾相等 && 子串是回文

嗯，这里要注意：基准情况一定要写对。我曾经见过一个新手，把基准情况写成「长度 == 0 返回 false」，结果空串永远判不成回文，调试了半天。

代码实现

直接上代码。我习惯用两个指针（left 和 right）来标记当前要比较的范围，这样不用每次都创建子串，效率更高。

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

// 递归判断回文
bool isPalindrome(const char *s, int left, int right) {
    // 基准情况：只剩 0 个或 1 个字符
    if (left >= right) {
        return true;
    }

    // 首尾字符不相等，直接返回 false
    if (s[left] != s[right]) {
        return false;
    }

    // 递归判断去掉首尾后的子串
    return isPalindrome(s, left + 1, right - 1);
}

int main() {
    char str[] = "level";

    if (isPalindrome(str, 0, strlen(str) - 1)) {
        printf("\"%s\" 是回文\n", str);
    } else {
        printf("\"%s\" 不是回文\n", str);
    }

    return 0;
}

这段代码的逻辑很清晰：

• left 和 right 分别指向字符串的首尾
• 每次比较 s[left] 和 s[right]
• 相等就递归，不相等就返回 false
• 当 left >= right 时，说明已经比较完了，返回 true

递归过程可视化

为了让你更直观地理解递归的「剥洋葱」过程，我画了一张流程图：

从图中可以看到，递归就像剥洋葱一样，一层层往里走。走到最里面发现「只剩一个字符了」，然后一层层把结果往回传。最终所有层都返回 true，整个字符串就是回文。

避坑指南

写递归判断回文时，有几个坑我踩过，分享给你：

• 空串和单字符：基准情况一定要覆盖 left >= right，而不是 left == right。因为如果字符串长度是偶数，最后会变成 left > right。
• 递归深度：C 语言的函数调用栈是有限的。如果一个字符串有 10000 个字符，递归深度就是 5000 层，很可能栈溢出。我在项目中遇到过这种情况，后来改成了迭代实现。
• 中文字符：C 语言里中文字符占多个字节，直接用 s[left] 比较会出问题。处理中文回文时，建议用宽字符或先转成 Unicode。

递归 vs 迭代

说到迭代，我顺便对比一下两种实现方式：

对比项	递归实现	迭代实现
代码长度	短，逻辑清晰	稍长，但也很直观
可读性	高，符合数学思维	中等，需要理解循环
性能	有函数调用开销	无额外开销，更快
栈安全	深度大时可能溢出	安全，只用一个循环

迭代版本的代码其实也不复杂，我贴出来供你参考：

bool isPalindromeIter(const char *s) {
    int left = 0;
    int right = strlen(s) - 1;

    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

你看，迭代版本用 while 循环，每次比较首尾，然后往中间移动。逻辑和递归完全一样，但没有函数调用开销。

总结

判断回文字符串的递归实现，是理解递归思想的一个绝佳例子。它完美体现了「大问题拆成小问题」的递归哲学。我个人建议你把这个例子背下来，以后面试或写代码时，随时能拿出来用。

最后提醒一句：递归虽好，但别忘了考虑栈深度。实际项目中，我一般先用递归写出清晰版本，如果性能有问题再改成迭代。先正确，再优化——这个顺序不会错。