Почему этот рекурсивный метод Java для подсчета двух символов работает?
В данный момент пытаюсь изучить Java. Я как раз решал несколько задач на рекурсию и наткнулся на одну, которая просила меня подсчитать количество вхождений подстроки «привет» в другую строку. Я искал рекурсивные способы сделать это, и я нашел код, который в основном делал то, что я хотел, и я мог перефразировать, но я не понимал, как/почему это работает. У меня не было проблем с другими проблемами рекурсии, и я понимаю концепцию вызова функции внутри ее тела, но то, как работает этот код, меня озадачивает. Пошаговое выполнение в отладчике меня просто смутило.
public int countHi(String str) {
int n = str.length();
if (n <= 1) return 0;
if (str.substring(0, 2).equals("hi"))
return countHi(str.substring(1)) + 1;
return countHi(str.substring(1));
}
Ответы 1
Обычно вся рекурсия сводится к двум основным выводам:
Базовый случай (или конечный случай): какая самая простая проблема? Где не нужно упрощать?
Рекурсивный случай: как вы решаете текущую проблему, используя более простое решение?
Базовый случай здесь, когда строка слишком короткая — строка менее двух символов, очевидно, не может содержать «привет».
Рекурсивный случай здесь заключается в том, что строка, начинающаяся с «привет», имеет на один «привет» больше, чем остальная часть строки, но строка, в которой не так много «привет», когда вы обрезаете начало.
Код кодирует эти два понимания.
о, это имеет больше смысла! Я был немного сбит с толку тем, почему код постоянно оценивает str.substring(1) и как это работает, но при дальнейшем рассмотрении это просто медленно разбивает строку на более мелкие строки размером <= 1, каждый раз разделяя один символ. .
Можете ли вы объяснить по-английски, что делает каждая строка кода одна за другой? Это поможет записать это.