Рекурсия в Java с примером решения задачи с LeetCode
Рекурсивные методы в Java — это методы, которые вызывают сами себя и требуют осторожности с их обращением.
Чтобы не увидеть «StackOverflowError» на экране, нужно помнить о двух штуках: базисе и шаге рекурсии.
Базис — это условие выхода из рекурсии, а шаг — это вызов методом самого себя с измененными параметрами.
Самый частый пример, который можно встретить в интернете при попытке найти информацию о рекурсии — нахождение факториала числа. Быстренько пройдемся по нему перед рассмотрением более интересной задачки с leetCode.
public int calculateFactorial(int x) {
int result = 1;
if (x == 1) {
return result;
}
return x * calculateFactorial(x - 1);
}Базис рекурсии в данном случае определяется условием «if», а шаг указан здесь — calculateFactorial(x — 1);
Что будет происходить в методе, если в качестве параметра х передадим значение 3? Сначала мы провалимся в условие calculateFactorial(3 — 1), затем снова в него же, но уже со значением calculateFactorial(2 — 1), затем упремся в базис:
if (x == 1) {
return result;
}И пойдем наверх: result = 2×1 = 2. И снова наверх (т.к. проваливались мы дважды): result = 3×2 = 6. 6 — финальный результат, который вернет метод.
Теперь рассмотрим более интересную задачку с leetCode. Если вы еще не знаете про классы, переменные, геттеры, сеттеры и конструкторы, то нужно сначала их изучить.
Условие задачи здесь: https://leetcode.com/problems/merge-two-sorted-lists/description/
Кратко: у нас есть два упорядоченных связанных списка, которые представлены набором чисел. Например:
Список 1: [1,4,8]
Список 2: [2,3,9,10]
Задача — объединить эти два списка в один.
Ожидаемый результат: [1,2,3,4,8,9,10]
Сами списки представлены классом ListNode с двумя переменными, сеттерами, геттерами и конструкторами (на leetCode сеттеров и геттеров нет, но в реальной мире лучше помнить об инкапсуляции):
public class ListNode {
private int val;
private ListNode next;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}Метод, который будет объединять наши два связанных списка в один, принимает на вход следующие параметры:
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {}Итак, сначала подумаем про базис — условие выхода из рекурсии. Упорядочивайте мы закончим тогда, когда в любом из списков не останется элементов, т.е.
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}Отлично, с базисом определились. Теперь нужно подумать о шаге рекурсии — здесь шаг рекурсии — это переход к следующему элементу, который представлен переменной private ListNode next в классе ListNode.
Если ни один из списков не пустой, то начинаем со сравнения первых элементов каждого списка, в нашем случае это 1 и 2.
1 < 2, соответсвенно, мы должны добавить в наш объединенный список число «1» и перейти к следующему элементу из list1, используя рекурсию. На Java это будет выглядеть следующим образом:
if (list1.getVal() < list2.getVal()) {
list1.getNext() = mergeTwoLists(list1.getNext(), list2);
return list1;
}Провалившись в рекурсию на второй строке, мы получаем на вход уже следующие списки:
Список 1: [4,8]
Список 2: [2,3,9,10]
И проходим снова по нашему циклу, сравнивая первые элементы каждого списка, только теперь 2 < 4, то есть list1.val < list2.val. А поэтому мы должны перейти к следующему элементу из «Списка 2», запишем в коде:
else {
list2.getNext() = mergeTwoLists(list1, list2.getNext());
return list2;
}Итого, наш метод должен выглядеть следующим образом:
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}
if (list1.getVal() < list2.getVal()) {
list1.setNext(mergeTwoLists(list1.getNext(), list2));
return list1;
} else {
list2.setNext(mergeTwoLists(list1, list2.getNext()));
return list2;
}
}Быстро пройдемся по каждому шагу рекурсии, просмотрев данные на входе:
Шаг 3:
Шаг 4:
Список 1: [4,8]
Список 2: [9,10]
Шаг 5:
Список 1: [8]
Список 2: [9,10]
Шаг 6:
Список 1: []
Список 2: [9,10]
На 6-ом шаге мы достигаем одного из базиса (условия выхода) рекурсии, и начинаем двигаться наверх.
Вернувшись на шаг 5, мы получаем list1.next = [9,10], , а сам list1 = [8,9,10].
На 4-ом шаге: list1.val = 4, list1.next = [8,9,10], возвращаем на шаг 3 — [4,8,9,10];
На 3-ий шаг мы заходили через list2.next, поэтому list2.next = [4,8,9,10], а list2.val = 3, возвращаем на 2-ой шаг: [3,4,8,9,10].
На 2-ом шаге, list2.next = [3,4,8,9,10], list2.val = 2, list2 = [2,3,4,8,9,10].
На 1-ом шаге, то есть на самом верху и финальном выходе из рекурсии, мы получим list1.next = [2,3,4,8,9,10], list1.val = 1, а list1 = [1,2,3,4,8,9,10] — это и есть результат работы метода.
Думаю, для полного понимания стоит несколько раз продебажить код через идею. Кстати, рекурсия бывает двух видов: хвостовая и головная. Если последнее, что выполняет метод — это вызов самого себя, значит это хвостовая рекурсия, иначе головная. Так, в случае с нахождением факториал мы использовали хвостовую рекурсию, а в случае с решением задачи про ListNode — головную.
Вот такая штука рекурсия :)
