递归查找最长回文子串：问题背景
在计算机科学中，回文是一个正读反读都相同的字符串，例如"madam"或"racecar"。查找给定字符串中的最长回文子串是一个经典的算法问题，常用于考察字符串处理和递归或动态规划思想。递归方法提供了一种直观的解决方案，但其实现细节往往容易出错，尤其是在处理边界条件和子问题依赖时。
初始递归尝试与常见误区
一个常见的递归思路是：如果字符串的首尾字符相同，那么它可能是一个回文。然后，我们递归地检查去除首尾字符后的内部子串。如果首尾字符不同，或者内部子串不满足条件，则最长回文子串可能存在于去除首字符或去除尾字符后的子串中。
考虑以下Java代码片段，它试图递归地计算最长回文子串的长度：
public static int palindrome(String str) {
str = str.toLowerCase(); // 转换为小写以进行不区分大小写的比较
if (str.length() == 0)
return 0;
if (str.length() == 1)
return 1;
// 如果首尾字符相同
if (str.charAt(0) == str.charAt(str.length() - 1)) {
// 递归获取内部子串的最长回文长度
int pal = palindrome(str.substring(1, str.length() - 1));
// 这里的逻辑是问题的关键所在
if (pal != 1 || str.length() <= 3) // 错误判断条件
return 2 + pal; // 错误返回
}
// 如果首尾字符不同，或上述条件不满足，则在子串中寻找
return Math.max(palindrome(str.substring(0, str.length() - 1)), palindrome(str.substring(1)));
}上述代码的意图是，当首尾字符匹配时，如果内部子串的最长回文长度pal不是1（即不是单个字符的回文）或者字符串长度小于等于3，就认为整个字符串是一个回文，其长度为 2 + pal。然而，这个判断条件存在一个严重的逻辑缺陷。
误区分析： 该代码未能正确识别“一个由相同首尾字符包围的子串，即使其内部包含回文，整个字符串也未必是回文”的情况。例如，对于字符串 "abca"：
- 'a' 和 'a' 匹配。
- 递归调用 palindrome("bc")，其返回的最长回文长度 pal 为 1（"b"或"c"）。
- 此时，pal (1) 不等于 1，且 str.length() (4) 不小于等于 3，因此 if (pal != 1 || str.length()
- 代码会执行 Math.max(palindrome("abc"), palindrome("bca"))。
- 但如果字符串是 "abacaba"，palindrome("bacab") 返回 5。此时 pal (5) 不等于 1，且 str.length() (7) 不小于等于 3，条件仍然不满足，导致无法直接返回 7。
问题的核心在于，只有当内部子串 str.substring(1, str.length() - 1) 本身就是一个完整的回文（即其最长回文长度等于其自身的长度），并且首尾字符也匹配时，整个 str 才能被视为一个回文。原代码中的 pal != 1 || str.length()
立即学习“Java免费学习笔记（深入）”；
修正后的递归算法
为了正确判断一个由相同首尾字符包围的字符串是否为回文，我们需要确保其内部子串也构成一个完整的回文。这意味着内部子串的最长回文长度必须等于其自身的长度。
修正后的递归逻辑如下：
public class LongestPalindromeFinder {
/**
* 递归查找给定字符串中最长回文子串的长度。
* 该方法不考虑性能优化（如备忘录化），仅展示纯递归逻辑。
*
* @param str 输入字符串
* @return 最长回文子串的长度
*/
public static int longestPalindromeRecursive(String str) {
// 转换为小写以进行不区分大小写的比较
str = str.toLowerCase();
// 基本情况：空字符串或单个字符
if (str.length() == 0) {
return 0;
}
if (str.length() == 1) {
return 1;
}
// 如果字符串的首尾字符相同
if (str.charAt(0) == str.charAt(str.length() - 1)) {
// 内部子串为 str.substring(1, str.length() - 1)
int innerSubstringLength = str.length() - 2; // 内部子串的实际长度
// 递归检查内部子串的最长回文长度
int innerPalindromeLength = longestPalindromeRecursive(str.substring(1, str.length() - 1));
// 关键修正：只有当内部子串本身就是一个完整的回文时，
// 即其最长回文长度等于内部子串的实际长度时，
// 整个当前字符串才构成一个回文。
if (innerPalindromeLength == innerSubstringLength) {
return str.length(); // 整个字符串是一个回文
}
}
// 如果首尾字符不相同，或者首尾相同但内部子串不是一个完整的回文，
// 则最长回文子串可能存在于：
// 1. 移除第一个字符后的子串中 (str.substring(0, str.length() - 1))
// 2. 移除最后一个字符后的子串中 (str.substring(1))
return Math.max(longestPalindrome 
