Рекурсия в Java

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

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

Первый пример: факториал

Факториал числа n — это n × (n-1) × (n-2) × … × 1. По определению, 0! = 1. Само определение рекурсивно: n! = n × (n-1)!.

Перевод на Java выглядит так:

public static int factorial(int n) {
  if (n == 0) return 1;            // base case
  return n * factorial(n - 1);      // recursive case
}

Вызов factorial(4) даёт:

factorial(4)
  = 4 * factorial(3)
  = 4 * 3 * factorial(2)
  = 4 * 3 * 2 * factorial(1)
  = 4 * 3 * 2 * 1 * factorial(0)
  = 4 * 3 * 2 * 1 * 1
  = 24

Каждый вызов стоит в стеке и ждёт, когда вернётся следующий. Когда factorial(0) наконец возвращает 1, ответы распространяются обратно по цепочке.

Базовый случай обязателен

Без базового случая методу нечем остановить рекурсию. Классическая ошибка:

public static int factorial(int n) {
  return n * factorial(n - 1);    // no base case
}

Рекурсия продолжается бесконечно — до тех пор, пока стек вызовов не исчерпается и JVM не бросит StackOverflowError. Базовый случай завершает цепочку; рекурсивный случай приближает к нему.

Другая классическая ошибка — базовый случай, которого рекурсия никогда не достигает:

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n + 1);    // wrong direction
}

factorial(4) здесь попытался бы вызвать factorial(5), factorial(6), … и упал бы. Рекурсивный вызов должен двигать аргумент ближе к базовому случаю.

Рекурсия на целых числах: обратный отсчёт

Простой второй пример для ясности — вывод чисел от n до 1:

public static void countdown(int n) {
  if (n <= 0) return;             // base case
  System.out.println(n);
  countdown(n - 1);                // recursive case
}

countdown(3) выводит 3, 2, 1. Поменяйте порядок, чтобы вывести 1, 2, 3:

public static void countup(int n) {
  if (n <= 0) return;
  countup(n - 1);                  // recurse first, print after
  System.out.println(n);
}

Та же рекурсия, другой порядок вывода — потому что рекурсивный вызов происходит до вывода. Урок: то, что делается до рекурсивного вызова, выполняется на пути вниз, а то, что после — на пути назад вверх.

Рекурсия на строках: переворачивание

Переворачивание строки можно представить как «взять первый символ, перевернуть остаток, добавить первый символ в конец»:

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

reverse("cat") → reverse("at") + 'c' → reverse("t") + 'a' + 'c' → "t" + 'a' + 'c' → "tac".

Это элегантно, но неэффективно — каждый рекурсивный вызов выделяет новую подстроку. Цикл с StringBuilder был бы быстрее. Рекурсия нередко является наиболее ясным выражением идеи, но не всегда самой быстрой реализацией.

Числа Фибоначчи и стоимость рекурсии

Последовательность Фибоначчи — 0, 1, 1, 2, 3, 5, 8, 13, …, определяемая как fib(n) = fib(n-1) + fib(n-2). Прямой перевод:

public static long fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

Это правильно, но работает экспоненциально медленно — fib(40) уже заметно тормозит, fib(50) — мучительно долго. Дерево рекурсии пересчитывает одни и те же подзадачи миллиарды раз (только fib(5) вызывает fib(2) трижды). Настоящее решение — мемоизация или обычный цикл.

Мемоизация сохраняет рекурсивную структуру, но кешируя каждый результат при первом вычислении, так что каждая подзадача выполняется лишь один раз:

public static long fibMemo(int n, long[] cache) {
  if (n < 2) return n;
  if (cache[n] != 0) return cache[n];      // already computed
  return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// call as: fibMemo(50, new long[51])

Обычный цикл полностью отказывается от рекурсии и использует константный объём памяти:

public static long fibLoop(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    long next = a + b;
    a = b;
    b = next;
  }
  return a;
}

Знать, когда рекурсия — неподходящий инструмент, не менее важно, чем знать, когда она уместна.

Рекурсия против итерации

Любой рекурсивный метод можно переписать как цикл, и любой цикл можно переписать как рекурсию — они одинаково мощны. Выбор определяется ясностью и стоимостью:

• Используйте рекурсию, когда сами данные рекурсивны (деревья, вложенные папки, JSON) или когда рекурсивное определение читается понятнее, чем цикл, как в случае factorial или reverse.
• Используйте цикл, когда рекурсия может быть достаточно глубокой, чтобы вызвать StackOverflowError, или когда итеративная версия не менее читаема и не несёт накладных расходов на вызов, как в случае fib.

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

StackOverflowError

Каждый ожидающий вызов использует часть стека JVM. При стандартном размере стека обычно можно вложить несколько тысяч вызовов до сбоя:

factorial(100000);    // StackOverflowError

Java не выполняет оптимизацию хвостовых вызовов — даже рекурсивный вызов, являющийся последним действием метода, всё равно занимает стековый фрейм. Если задача может потребовать очень глубокой рекурсии, переключитесь на цикл или используйте явный Deque в качестве собственного стека.

Рабочий пример

Что дальше

Вы определяли методы, передавали параметры, перегружали имена и использовали рекурсию. Следующая концепция — область видимости: какие части метода видят какие переменные и что происходит, когда имя встречается более чем в одном месте. Читайте дальше в главе об области видимости переменных.

Практика