Блог

Главная - Вопросы по программированию - Ошибка палиндромного стекового потока

Ошибка палиндромного стекового потока

#java #algorithm #recursion #palindrome

#java #алгоритм #рекурсия #палиндром

Вопрос:

Я попытался использовать рекурсию для решения проблемы с палиндромом. Я получил исключение в потоке «main» java.lang.Ошибка StackOverflowError в java.lang.Строка.подстрока(String.java:1969) в Main.isPalindrome(Main.java:160)

Однако я не знаю, как это исправить.

 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 amp;amp; check2) {
                if (ch1 == ch2) {
                    String shorter = s.substring(1, len - 1);
                    return isPalindrome(shorter);
                }
                else {
                    return false;
                }
            }
            else if (!check1 amp;amp; check2) {
                String shorter = s.substring(1);
                return isPalindrome(shorter);
            }
            else if (!check2 amp;amp; check1) {
                String shorter = s.substring(0, len - 1);
                return isPalindrome(shorter);
            }
            else {
                String shorter = s.substring(1, len - 1);
                return isPalindrome(shorter);
            }
        }
    }

Комментарии:

1. здесь ваш код предполагает, что входная строка будет нечетной длины. Проверьте, равна ли длина 2 и в начальном блоке, а затем проверьте 0-ю и 1-ю позиции

2. Я попробовал System.out.print(isPalindrome(«sb, bbs»)); System.out.print(isPalindrome(«, bbs»)); System.out.print(isPalindrome(«sbbs»));

3. Но все они верны

Ответ №1:

В вашей логике нет ничего плохого. Просто существует ограниченный объем памяти для хранения кадров стека и, следовательно, ограниченное количество уровней рекурсии. Когда StackOverflowError будет выброшена достаточно большая входная строка.

Я предлагаю отказаться от этой рекурсивной реализации и вместо этого использовать цикл.

Ответ №2:

Трудно сказать, не зная точно, какая строка равна 160. Тем не менее, вы, вероятно, вызываете это с теми же аргументами, что и сам метод, и, следовательно, нет ничего, что могло бы положить конец вашей рекурсии.