Рекурсивные методы в 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: 

• Список 1: [4,8]

• Список 2:  [3,9,10]

Шаг 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 — головную.

Вот такая штука рекурсия :)