Блог

Главная - Вопросы по программированию - Кто-нибудь может объяснить этот рекурсивный метод Java, который переворачивает строку?

Кто-нибудь может объяснить этот рекурсивный метод Java, который переворачивает строку?

#java #string #recursion #substring #charat

#java #строка #рекурсия #подстрока #charat

Вопрос:

итак, я младший в колледже, пытаюсь понять рекурсию. Я понимаю общую концепцию, но не то, как она правильно реализована. Я нашел этот чрезвычайно простой код и, похоже, просто не могу понять, как работает последняя строка (рекурсия). Любая помощь и объяснение были бы потрясающими, спасибо! (также скоро финал, и я нервничаю)

 public static String reverse(String s) {
    if (s.isEmpty())
        return s;
    return reverse(s.substring(1))   s.charAt(0);
}

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

1. Возьмите лист бумаги, используйте входную строку abc , а затем напишите, что происходит со всеми рекурсивными вызовами. Это действительно лучшее упражнение, которое вы можете сделать здесь, чтобы научиться.

2. Как посоветовал @TimBiegeleisen , я думаю, что вам поможет выполнение одного прогона. Возьмите строку ( abcdefg или что-нибудь несимметричное) и запустите этот код с дополнительным System.out.println(s); перед возвратом: затем вы должны понять, как с ним манипулируют

Ответ №1:

Процесс рекурсии удаляет один за другим символы, используя substring , поскольку substring принимает начальный индекс, который в вашем случае равен 1, поэтому, если наша строка «ABC», то «ABC».substring(1), тогда substring вернет «BC», Поэтому в вашем случае обратная обработка выполняется с помощью substring, давайте возьмем, что наш ввод равен»abcd» для обратного метода

тогда процесс будет похож на обратный метод в качестве рекурсии

 bcd -> 1st reverse will call with this value
cd -> then reverse will call with cd
d -> then reverse will call with d
"" -> then reverse will call with "" as its blank string so reverse will terminate

как только обратный метод достигнет оператора isEmpty, запустится s.charAt(0), который добавит в конце возвращаемого вывода из обратного метода, чтобы он изменил вывод следующим образом

 d
dc
dcb
dcba

таким образом, весь процесс будет похож:

 input to reverse method :bcd
input to reverse method :cd
input to reverse method :d
input to reverse method : "" empty string
result received from reverse method  
After modified result with return value from reverse method and charAt(0) operation : d
result received from reverse method  d
After modified result with return value from reverse method and charAt(0) operation : dc
result received from reverse method  dc
After modified result with return value from reverse method and charAt(0) operation : dcb
result received from reverse method  dcb
After modified result with return value from reverse method and charAt(0) operation : dcba

Ответ №2:

Вот итеративная версия того же алгоритма для наглядности, которая перебирает символы строки в порядке встречаемости и объединяет их в новую строку в обратном порядке, меняя местами слагаемые:

 public static String reverse(String str) {
    String revStr = "";
    for (char ch : str.toCharArray()) {
        revStr = ch   revStr;
    }
    return revStr;
}
 
 public static void main(String[] args) {
    System.out.println(reverse("some text string"));
}

Вывод:

 gnirts txet emos