C++ 递归算法判断字符串是否为回文

判断一个字符串是否为回文串，可以使用递归算法。

递归模型

设字符串的长度为 n，则递归模型如下：

如果 n=0 或 n=1，则字符串是回文串；
否则，如果第一个字符和最后一个字符相同，并且去掉第一个和最后一个字符后的子串也是回文串，则字符串是回文串，否则不是回文串。

递归程序

bool isPalindrome(char str[], int left, int right) {
    if (left >= right) {
        return true;
    }
    if (str[left] != str[right]) {
        return false;
    }
    return isPalindrome(str, left+1, right-1);
}

//调用方式：isPalindrome(str, 0, strlen(str)-1)

代码说明：

isPalindrome(char str[], int left, int right) 函数接收三个参数：
- str：存放字符串的字符数组；
- left：字符串的起始位置索引；
- right：字符串的结束位置索引；
函数首先判断 left 是否大于等于 right，如果是，则说明字符串为空或只有一个字符，直接返回 true。
否则，判断 str[left] 是否等于 str[right]，如果不相等，则直接返回 false。
如果相等，则递归调用 isPalindrome 函数，将 left 加 1，right 减 1，判断去掉第一个和最后一个字符后的子串是否为回文串。

调用方式：

在调用 isPalindrome 函数时，将字符数组 str、起始位置 0 和结束位置 strlen(str)-1 传递给函数即可。

例如：

char str[] = "abccba";
bool result = isPalindrome(str, 0, strlen(str)-1);

if (result) {
    cout << "字符串是回文串" << endl;
} else {
    cout << "字符串不是回文串" << endl;
}

输出：

字符串是回文串