递归实现字符串回文检测为何返回false？

核心问题分析 #

你的代码返回false的原因是递归调用未传递返回结果，导致最终比较的不是完整反转后的字符串：

• 在stringInterchange方法的if(index >= 0)块中，你调用了递归方法但没有返回其结果，当前函数会继续执行到最后的return toBeModified.equals(check);语句
• 此时的toBeModified只是当前递归层拼接的部分字符串（比如第一次调用时，拼接完第一个字符"A"就执行return，而不是等递归完成拿到完整的反转字符串），自然和原字符串不相等，返回false

修复后的代码 #

修改递归调用逻辑，让每一层递归都返回下层递归的结果，只有当递归完成（index < 0）时才执行最终的字符串比较：

public class StringPalindromeCheckUsingRecursion {

    public static void main(String[] args) {
        System.out.println(isPalindrome("ABBBBA"));
    }

    public static boolean isPalindrome(String str) {
        int i = str.length() - 1;
        return stringInterchange(str, "", str, i);
    }

    public static boolean stringInterchange(String original, String toBeModified, String check, int index) {
        if(index >= 0) {
            char character = original.charAt(index);
            toBeModified = toBeModified + character;
            // 返回递归调用的结果，终止当前层后续执行
            return stringInterchange(original, toBeModified, check, index - 1);
        }
        // 递归完成，此时toBeModified是完整的反转字符串
        return toBeModified.equals(check);
    }
}

优化建议（可选） #

由于Java中String是不可变对象，每次拼接都会生成新字符串，递归次数较多时性能较差。可以改用StringBuilder来优化拼接操作：

public class StringPalindromeCheckUsingRecursion {

    public static void main(String[] args) {
        System.out.println(isPalindrome("ABBBBA"));
    }

    public static boolean isPalindrome(String str) {
        int i = str.length() - 1;
        return stringInterchange(str, new StringBuilder(), str, i);
    }

    public static boolean stringInterchange(String original, StringBuilder toBeModified, String check, int index) {
        if(index >= 0) {
            char character = original.charAt(index);
            toBeModified.append(character);
            return stringInterchange(original, toBeModified, check, index - 1);
        }
        return toBeModified.toString().equals(check);
    }
}

内容的提问来源于stack exchange，提问作者Jashin Bhatia