Рекурсия

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

Рекурсивный метод

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

void countdown(int n) {
    if (n == 0) {
        IO.println("Старт!");
        return;
    }
    IO.println(n);
    countdown(n - 1);
}
 
void main() {
    countdown(3);
}

Результат:

3
2
1
Старт!

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

У каждого рекурсивного метода есть две части. Базовый случай — условие, при котором метод отвечает сразу, без нового вызова. Рекурсивный шаг — вызов себя с более простыми данными. Факториал n! — произведение чисел от 1 до n — хорошо показывает обе части:

long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
 
void main() {
    IO.println(factorial(5));
    IO.println(factorial(20));
}

Результат:

120
2432902008176640000

factorial(5) превращается в 5 * factorial(4), затем в 5 * 4 * factorial(3) и так далее, пока не дойдёт до factorial(1), который сразу возвращает 1.

Стек вызовов

Каждый незавершённый вызов хранится в стеке вызовов — области памяти, где Java запоминает, куда вернуться и какие значения были у локальных переменных. Код после рекурсивного вызова выполняется на обратном пути, от самого глубокого вызова к первому:

void dive(int depth) {
    if (depth > 3) {
        return;
    }
    IO.println("Вниз: " + depth);
    dive(depth + 1);
    IO.println("Вверх: " + depth);
}
 
void main() {
    dive(1);
}

Результат:

Вниз: 1
Вниз: 2
Вниз: 3
Вверх: 3
Вверх: 2
Вверх: 1

Рекурсия и цикл

Любую рекурсию можно переписать циклом, и наоборот. Сумма цифр числа выглядит рекурсивно короче всего: последняя цифра плюс сумма цифр остального числа:

int digitSum(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + digitSum(n / 10);
}
 
void main() {
    IO.println(digitSum(2025));
}

Результат:

9

Для простых повторений цикл обычно понятнее и быстрее. Рекурсию выбирают, когда сама задача рекурсивна.

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

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

int sum(int n) {
    return n + sum(n - 1);
}
 
void main() {
    IO.println(sum(3));
}

Результат:

Exception in thread "main" java.lang.StackOverflowError

Начинайте рекурсивный метод с базового случая и проверяйте, что каждый вызов приближает к нему данные. Как устроен стек и чем он отличается от кучи, рассказано в уроке Память и сборка мусора.