Рекурсия в Java - Вопросы

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

Любой корректный рекурсивный метод состоит из двух частей:

1. Базовый случай — условие, при котором метод возвращает результат без нового вызова себя. Он обязателен и должен быть достижим для всех допустимых аргументов: базу пишут неравенством if (n <= 1), а не равенством if (n == 1), иначе вызов с нулём или отрицательным числом «проскочит» базу и приведёт к StackOverflowError.

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

static long factorial(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Факториал не определён для: " + n);
    }
    if (n <= 1) {          // базовый случай: 0! = 1 и 1! = 1
        return 1;
    }
    return n * factorial(n - 1); // рекурсивный случай
}

Рекурсия естественнее цикла для обхода деревьев и графов, алгоритмов «разделяй и властвуй» (быстрая сортировка, сортировка слиянием, бинарный поиск) и перебора с возвратом (backtracking).

При каждом вызове метода JVM создаёт в стеке вызовов новый кадр (stack frame) с аргументами, локальными переменными и адресом возврата. Кадр удаляется только тогда, когда метод завершился, поэтому при рекурсии все промежуточные кадры одновременно висят в памяти, пока вызовы не дойдут до базового случая.

StackOverflowError возникает, когда суммарный размер кадров превысил размер стека потока. Это Error, а не Exception: ловить его в catch и продолжать работу нельзя — состояние программы после переполнения не определено.

Фиксированного лимита глубины не существует. Она зависит от:

• размера стека потока — по умолчанию обычно 512 КБ – 1 МБ, задаётся флагом JVM -Xss (например, java -Xss2m RecursionExample);
• размера кадра — чем больше у метода параметров и локальных переменных, тем меньше вызовов помещается в стек.

На практике простой метод выдерживает порядка нескольких тысяч — десятков тысяч вложенных вызовов, но закладываться на конкретное число нельзя. Увеличение -Xss — временная мера: если глубина зависит от входных данных, алгоритм переписывают на цикл.

У виртуальных потоков (Java 21+) стек хранится в куче и растёт по мере необходимости, поэтому -Xss на них не влияет, но и там глубина конечна.

Прямая рекурсия — метод вызывает сам себя.

Косвенная (взаимная) рекурсия — метод A вызывает B, а B снова вызывает A:

static boolean isEven(int n) {
    return n == 0 ? true : isOdd(n - 1);
}

static boolean isOdd(int n) {
    return n == 0 ? false : isEven(n - 1);
}

Хвостовая рекурсия — рекурсивный вызов является последней операцией метода, после возврата делать уже нечего:

static long factorialTail(int n, long acc) {
    if (n <= 1) {
        return acc;
    }
    return factorialTail(n - 1, n * acc);
}

Java хвостовую рекурсию не оптимизирует. Спецификация JVM не требует оптимизации хвостовых вызовов (TCO), и HotSpot её не выполняет: для каждого вызова всё равно создаётся новый кадр стека. В Scala и Kotlin компилятор превращает такой вызов в цикл, в Java — нет. Поэтому хвостовая форма в Java не защищает от StackOverflowError, и при большой глубине её переписывают циклом вручную. Это частый вопрос на собеседовании.

Наивная реализация делает два рекурсивных вызова на каждом шаге, из-за чего одни и те же значения пересчитываются снова и снова. Сложность получается экспоненциальной — O(2ⁿ): fibonacci(40) выполняет более 300 миллионов вызовов и заметно подвисает.

static long fibonacci(int n) {
    if (n <= 1) {           // базовые случаи: F(0) = 0, F(1) = 1
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Мемоизация — кеширование уже вычисленных значений, чтобы каждое считалось ровно один раз. Сложность падает до O(n):

private static final long[] CACHE = new long[93]; // F(92) - максимум для long

static long fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    if (CACHE[n] != 0) {   // значение уже посчитано
        return CACHE[n];
    }
    CACHE[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return CACHE[n];
}

Тот же результат можно получить вообще без рекурсии — обычным циклом за O(n) времени и O(1) памяти.

Любую рекурсию можно переписать циклом, и наоборот. Разница — в памяти, скорости и читаемости:

• Память: рекурсия — O(глубины) в стеке вызовов (кадр на каждый вызов), цикл — O(1).
• Скорость: цикл быстрее, у рекурсии есть накладные расходы на вызов метода и возврат.
• Риск отказа: рекурсия при большой глубине падает с StackOverflowError, у цикла стек не растёт.
• Читаемость: рекурсия выигрывает на деревьях, графах и backtracking, цикл — на линейных проходах.

Линейную рекурсию (факториал, Фибоначчи) заменяют обычным циклом с накоплением результата:

static long factorialIterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Для обхода деревьев и графов заводят явный стек: ArrayDeque для обхода в глубину или Queue для обхода в ширину. Вложенность переезжает из стека потока в кучу, и глубина ограничена уже доступной памятью, а не флагом -Xss:

static void printTree(File root) {
    Deque<File> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        File current = stack.pop();
        System.out.println(current.getName());
        File[] children = current.listFiles();
        if (children != null) {
            for (File child : children) {
                stack.push(child);
            }
        }
    }
}