Рекурсия

Некоторые задачи удобно описывать через них самих. Возьмём сумму чисел от 1 до n. Её можно определить двумя правилами:

• сумма до нуля равна 0;
• сумма до n равна n плюс сумма до n - 1.

Метод на Java повторяет это определение дословно и вызывает сам себя:

public class Main {
    static int sum(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(3)); // 6
        System.out.println(sum(5)); // 15
    }
}

Вернёмся к кухонному прибору и посмотрим, как он считает sum(3):

1. Прибор sum получил 3, но сразу ответа не знает.
2. Он ставит рядом такой же прибор, отдаёт ему 2 и ждёт результат, чтобы прибавить к нему свои 3.
3. Второй прибор так же поручает работу третьему с 1, а тот — четвёртому с 0.
4. Четвёртый отвечает 0 сразу, никого не вызывая.
5. Ответы идут обратно: третий возвращает 1 + 0, второй — 2 + 1, первый — 3 + 3, то есть 6.

Две ветки рекурсивного метода

Рекурсия — это вызов методом самого себя. В рекурсивном методе всегда есть две ветки.

Базовый случай

Ветку, где метод завершается без нового вызова, называют базовым случаем. В sum это if (n == 0) { return 0; }: вызов sum(0) сразу возвращает 0.

Без базового случая вызовы не закончатся никогда. Поэтому каждый новый вызов должен приближать аргумент к базовому случаю: здесь n уменьшается на единицу.

Рекурсивный шаг

Строка return n + sum(n - 1); вызывает тот же метод с аргументом на единицу меньше. Вызов sum(3) ждёт результата sum(2), тот ждёт sum(1), и так до sum(0). Только потом каждый ждущий вызов прибавляет свою n и возвращает ответ.

Стек вызовов

Пока вызов не завершился, Java хранит его параметры и место, куда вернуть результат. Эти записи лежат в стеке вызовов: у каждого незавершённого вызова своя запись. Стек похож на стопку тарелок:

• новый вызов кладёт тарелку сверху;
• завершённый вызов снимает верхнюю тарелку.

Поэтому у каждого вызова sum своя переменная n. В стопке одновременно лежат записи с n, равной 3, 2, 1 и 0, и друг другу они не мешают. Нажимайте «Следующий шаг» и следите за столбцом «рамки вызовов»: каждая рамка в нём — запись одного вызова. Стопка растёт до sum(0), а потом разбирается сверху вниз.

Результаты возвращаются в обратном порядке: вызов, начатый последним, завершается первым.

Здесь картинка с приборами неточна. Приборов понадобилось бы четыре, а метод sum в программе один. Для каждого вызова отдельно хранятся только его данные: своя n и место, куда вернуть результат.

StackOverflowError

Стек вызовов не бесконечен. Если базового случая нет или вызовы до него не доходят, записи копятся, пока место не кончится. Тогда программа останавливается с ошибкой StackOverflowError, и её название значит «переполнение стека». Обычно это случается через тысячи или десятки тысяч вызовов: точное число зависит от настроек JVM.

Этот вопрос часто задают на собеседовании: «Когда возникает StackOverflowError?» Ответ: когда цепочка вызовов слишком длинная или не останавливается, потому что базовый случай недостижим.

Цикл вместо рекурсии

Ту же сумму можно посчитать циклом:

static int sumLoop(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total = total + i;
    }
    return total;
}

Цикл не вызывает новых методов, поэтому стопка не растёт, сколько бы ни было шагов. Java не превращает рекурсию в цикл сама, и для очень длинных цепочек пишут цикл. Рекурсия удобна там, где задача сама устроена через меньшую копию себя.

Частая ошибка

Метод вызвали с аргументом, для которого базовый случай недостижим:

System.out.println(sum(-1)); // ✗

Exception in thread "main" java.lang.StackOverflowError

От -1 цепочка идёт к -2, -3 и дальше, а n == 0 не наступает никогда. Каждый вызов кладёт в стек новую запись, пока место не кончится. Делайте базовый случай достижимым для любого аргумента: например, if (n <= 0) { return 0; }.

Главное

• Рекурсивный метод вызывает сам себя, и ему нужен базовый случай, который завершается без нового вызова.
• Каждый незавершённый вызов занимает запись в стеке вызовов, поэтому у каждого вызова sum своя n.
• Результаты возвращаются в обратном порядке: вызов, начатый последним, завершается первым.
• Если базовый случай недостижим, стек переполняется, и программа останавливается с StackOverflowError.