palindrome StackOverflow Error

Question

I tried to use recursion to solve the palindrome problem. I got a Exception in thread "main" java.lang.StackOverflowError at java.lang.String.substring(String.java:1969) at Main.isPalindrome(Main.java:160)

However, I don't know how to fix it.

public static boolean isPalindrome(String s) {
        int len = s.length();
        if (len <= 1) return true;
        else {
            char ch1 = Character.toLowerCase(s.charAt(0));
            char ch2 = Character.toLowerCase(s.charAt(len - 1));
            boolean check1 = Character.isLetter(ch1) || Character.isDigit(ch1);
            boolean check2 = Character.isLetter(ch2) || Character.isDigit(ch2);
            if (check1 && check2) {
                if (ch1 == ch2) {
                    String shorter = s.substring(1, len - 1);
                    return isPalindrome(shorter);
                }
                else {
                    return false;
                }
            }
            else if (!check1 && check2) {
                String shorter = s.substring(1);
                return isPalindrome(shorter);
            }
            else if (!check2 && check1) {
                String shorter = s.substring(0, len - 1);
                return isPalindrome(shorter);
            }
            else {
                String shorter = s.substring(1, len - 1);
                return isPalindrome(shorter);
            }
        }
    }

Answer 1

Nothing wrong with your logic. It's just that there's a limited amount of memory to keep the stack frames, and therefore a limited number of recursion levels. When the input string is large enough StackOverflowError would be thrown.

My suggestion is to abandon this recursive implementation and use a loop instead.