Рекурсия в Java

factorial(0) — вроде бы тривиальный случай: 0! = 1. Но если базовый случай написан как if (n == 1), метод не вернёт 1 — он упадёт с StackOverflowError. Рекурсия в Java прощает многое, кроме недостижимого базового случая.

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

Что такое рекурсия в Java

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

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

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

Задачи, где рекурсия выглядит естественнее цикла:

• обход деревьев (файловая система, DOM, JSON), графов и вложенных структур;
• алгоритмы «разделяй и властвуй»: быстрая сортировка, сортировка слиянием, бинарный поиск;
• перебор с возвратом (backtracking): расстановка ферзей, судоку, генерация перестановок;
• учебные математические задачи: факториал, числа Фибоначчи, сумма цифр, возведение в степень.

Как работает рекурсия: стек вызовов

При каждом вызове метода JVM создаёт в стеке вызовов новый кадр (stack frame). В кадре хранятся:

• аргументы метода;
• локальные переменные;
• адрес возврата — куда продолжить выполнение после завершения метода.

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

Посмотрим, как разворачивается и сворачивается стек для factorial(5):

factorial(5) -> 5 * factorial(4)      // кадр 1
   factorial(4) -> 4 * factorial(3)   // кадр 2
      factorial(3) -> 3 * factorial(2)// кадр 3
         factorial(2) -> 2 * factorial(1) // кадр 4
            factorial(1) -> 1         // кадр 5: базовый случай, разворот назад
         factorial(2) = 2 * 1  = 2
      factorial(3) = 3 * 2  = 6
   factorial(4) = 4 * 6  = 24
factorial(5) = 5 * 24 = 120

Умножение n * factorial(n - 1) выполняется после возврата вложенного вызова — именно поэтому кадр нельзя освободить раньше. Глубина стека здесь равна n.

Базовый случай и рекурсивный вызов

Базовый случай обязателен, и его недостаточно просто написать — он должен быть достижим для всех допустимых аргументов. Классический промах: базой объявлено n == 1, а метод вызывают с нулём или отрицательным числом. Условие никогда не сработает, аргумент уходит в минус, и стек переполняется.

Факториал: рекурсивный метод

Факториал числа n равен произведению всех натуральных чисел от 1 до n:

n! = n × (n - 1) × (n - 2) × ... × 1, а по соглашению 0! = 1.

Рекурсивная реализация в Java:

public class RecursionExample {

    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); // рекурсивный случай
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));   // 5! = 120
        System.out.println("0! = " + factorial(0));   // 0! = 1
        System.out.println("20! = " + factorial(20)); // 20! = 2432902008176640000
    }
}

Разбор:

• n <= 1 — базовый случай, он же обрабатывает 0!;
• factorial(n - 1) — рекурсивный вызов с уменьшенным аргументом;
• проверка n < 0 превращает бесконечную рекурсию в понятное исключение.

Числа Фибоначчи и мемоизация

Последовательность Фибоначчи задаётся правилом F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Прямой перевод формулы в код выглядит так:

public class FibonacciExample {

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

    public static void main(String[] args) {
        System.out.println(fibonacci(6)); // 8
    }
}

Код читается легко, но у него есть серьёзная проблема: два рекурсивных вызова на каждом шаге дают экспоненциальную сложность O(2ⁿ). Одни и те же значения пересчитываются снова и снова: fibonacci(40) выполняет более 300 миллионов вызовов и заметно «подвисает».

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

public class FibonacciMemo {

    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];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(50)); // 12586269025 - мгновенно
    }
}

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

static long fibonacciIterative(int n) {
    long prev = 0;
    long curr = 1;
    if (n <= 1) {
        return n;
    }
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

Виды рекурсии: прямая, косвенная, хвостовая

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

Косвенная (взаимная) рекурсия — метод 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); // ничего не выполняется после возврата
}

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

Рекурсия и итерация: что выбрать

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

Итеративный факториал для сравнения — ни одного лишнего кадра в стеке:

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

StackOverflowError и глубина рекурсии

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

Что определяет предельную глубину:

• Размер стека потока. По умолчанию обычно 512 КБ – 1 МБ, задаётся флагом JVM -Xss, например -Xss2m. Для отдельного потока размер можно передать в конструктор Thread.
• Размер кадра. Чем больше у метода параметров и локальных переменных, тем толще кадр и тем меньше вызовов помещается.

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

java -Xss2m RecursionExample

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

// обход дерева каталогов без рекурсии
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);
            }
        }
    }
}

На чём чаще всего ошибаются

• Нет базового случая или он недостижим (n == 1 вместо n <= 1) — мгновенный StackOverflowError.
• Аргумент не приближается к базе. Опечатка вроде factorial(n) вместо factorial(n - 1) даёт бесконечный цикл вызовов.
• Экспоненциальное дублирование вызовов — наивный Фибоначчи. Решается мемоизацией или переходом на цикл.
• Глубина зависит от входных данных. Рекурсивный обход списка на миллион элементов упадёт, хотя на тестовых десяти работал.
• Общее изменяемое состояние. Статические поля, которые меняются между вызовами, ломают логику при возврате из рекурсии; передавайте состояние параметрами.
• Ловля StackOverflowError в catch вместо исправления алгоритма.
• Циклические структуры данных. Обход графа со связями по кругу без множества посещённых узлов зациклит рекурсию.

Задача для практики

Напишите рекурсивные методы:

1. static int sumOfDigits(int n) — сумма цифр числа. Для 1234 результат 10. Подсказка: базовый случай n < 10, рекурсивный шаг — n % 10 + sumOfDigits(n / 10).
2. static String reverse(String s) — переворот строки. Базовый случай — пустая строка или строка из одного символа.
3. static boolean isPalindrome(String s) — проверка палиндрома через сравнение первого и последнего символов.

Для каждого метода отдельно проверьте граничные значения: 0, пустую строку и null.

Заключение

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

Что важно запомнить:

• базовый случай обязателен и должен быть достижим для всех аргументов;
• каждый рекурсивный вызов обязан приближать вычисление к базовому случаю;
• JVM не оптимизирует хвостовую рекурсию — стек расходуется всегда;
• наивную рекурсию с повторяющимися вычислениями спасает мемоизация;
• если глубина зависит от входных данных — переходите на цикл с явным стеком.