Что происходит при неуправляемой рекурсии

Что происходит при неуправляемой рекурсии

Неуправляемая рекурсия (Uncontrolled Recursion) — это ситуация, когда рекурсивная функция вызывает сама себя без правильного условия выхода, приводя к бесконечному накоплению вызовов в стеке вызовов (Call Stack). Это приводит к критической ошибке StackOverflowError.

Как работает стек вызовов (Call Stack)

Когда метод вызывает другой метод, информация о вызове сохраняется в стеке:

public class RecursionExample {
    public static void methodA() {
        methodB(); // Кадр A добавляется в стек
    }
    
    public static void methodB() {
        methodC(); // Кадр B добавляется в стек
    }
    
    public static void methodC() {
        System.out.println("Done"); // Кадр C добавляется в стек
    }
}

Стек вызовов:

┌─────────┐
│ methodC │  <- Текущий вызов
├─────────┤
│ methodB │
├─────────┤
│ methodA │
├─────────┤
│ main    │
└─────────┘

Когда методC завершается, его кадр удаляется из стека и возврат идет в methodB.

Неправильная рекурсия — пример

// ОШИБКА: Нет условия выхода!
public static void infiniteRecursion() {
    System.out.println("Calling myself...");
    infiniteRecursion(); // Вызывает сама себя бесконечно
}

// Вызов
public static void main(String[] args) {
    infiniteRecursion();
}

Что происходит:

Стек растет:
┌─────────────────────┐
│ infiniteRecursion   │  <- Вызов 1000000
├─────────────────────┤
│ infiniteRecursion   │  <- Вызов 999999
├─────────────────────┤
│ infiniteRecursion   │  <- Вызов 999998
├─────────────────────┤
│ ...                 │
├─────────────────────┤
│ infiniteRecursion   │  <- Вызов 2
├─────────────────────┤
│ infiniteRecursion   │  <- Вызов 1
├─────────────────────┤
│ main                │
└─────────────────────┘

В какой-то момент стек переполняется!
Exception in thread "main" java.lang.StackOverflowError

StackOverflowError — критическая ошибка

Когда стек переполняется, JVM выбрасывает StackOverflowError:

public class StackOverflowDemo {
    public static void recursion(int count) {
        System.out.println("Count: " + count);
        recursion(count + 1); // Бесконечная рекурсия
    }
    
    public static void main(String[] args) {
        try {
            recursion(1);
        } catch (StackOverflowError e) {
            System.err.println("ОШИБКА: Переполнение стека!");
            System.err.println("Стек вырос слишком большим");
            e.printStackTrace();
        }
    }
}

Вывод:

Count: 1
Count: 2
Count: 3
...
Count: 15000 (примерно)
ОШИБКА: Переполнение стека!
java.lang.StackOverflowError
    at StackOverflowDemo.recursion(StackOverflowDemo.java:3)
    at StackOverflowDemo.recursion(StackOverflowDemo.java:4)
    at StackOverflowDemo.recursion(StackOverflowDemo.java:4)
    ... (еще тысячи одинаковых строк)

Размер стека

В Java стек имеет ограниченный размер (по умолчанию 1 MB на одноядерной машине):

# Каждый метод занимает место в стеке
# На одинарных машинах: ~1-2 MB по умолчанию
# На 64-разрядных: ~1 MB

# Можно изменить размер стека при запуске
java -Xss2m MyProgram # Установить стек 2 MB
java -Xss512k MyProgram # Или 512 KB

Правильная рекурсия с условием выхода

// ПРАВИЛЬНО: Есть условие выхода (base case)
public static int factorial(int n) {
    // Base case — условие выхода
    if (n <= 1) {
        return 1;
    }
    
    // Recursive case — рекурсивный вызов
    return n * factorial(n - 1);
}

public static void main(String[] args) {
    System.out.println(factorial(5)); // 120
    System.out.println(factorial(1000)); // Большие значения тоже ОК
}

Последовательность вызовов:

factorial(5)
├─ factorial(4)
├──── factorial(3)
├────── factorial(2)
├────────── factorial(1)
└────────────── return 1

Частые ошибки рекурсии

Ошибка 1: Забыли условие выхода

// ОШИБКА: Нет base case
public static int fibonacci(int n) {
    return fibonacci(n - 1) + fibonacci(n - 2); // Бесконечно!
}

// ПРАВИЛЬНО: Есть base case
public static int fibonacci(int n) {
    if (n <= 1) return n; // Base case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Ошибка 2: Условие выхода никогда не достигается

// ОШИБКА: n никогда не будет = 10
public static void countdown(int n) {
    if (n == 10) {
        return;
    }
    System.out.println(n);
    countdown(n - 1); // n только уменьшается, никогда не станет 10
}

// ПРАВИЛЬНО: Условие достижимо
public static void countdown(int n) {
    if (n <= 0) { // Достижимое условие
        return;
    }
    System.out.println(n);
    countdown(n - 1);
}

Ошибка 3: Рекурсия слишком глубокая

// ПРОБЛЕМА: Может переполнить стек для большого n
public static long sum(int[] arr, int index) {
    if (index == arr.length) return 0;
    return arr[index] + sum(arr, index + 1);
}

// Вызов с большим массивом
int[] largeArray = new int[100000];
sum(largeArray, 0); // StackOverflowError!

// РЕШЕНИЕ: Использовать iterative approach
public static long sumIterative(int[] arr) {
    long total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

Отладка рекурсии

public static int fibonacci(int n, int depth) {
    // Вывод для отладки
    System.out.println("  ".repeat(depth) + "fib(" + n + ")");
    
    // Base case
    if (n <= 1) {
        System.out.println("  ".repeat(depth) + "-> " + n);
        return n;
    }
    
    // Рекурсивные вызовы
    int result = fibonacci(n - 1, depth + 1) + fibonacci(n - 2, depth + 1);
    System.out.println("  ".repeat(depth) + "-> " + result);
    return result;
}

public static void main(String[] args) {
    fibonacci(4, 0);
}

Вывод:

fib(4)
  fib(3)
    fib(2)
      fib(1)
      -> 1
      fib(0)
      -> 0
    -> 1
    fib(1)
    -> 1
  -> 2
  fib(2)
    ...

Мониторинг стека

public class StackMonitor {
    public static void recursion(int count) {
        // Получить информацию о стеке
        long maxMemory = Runtime.getRuntime().maxMemory();
        long usedMemory = Runtime.getRuntime().totalMemory() - 
                         Runtime.getRuntime().freeMemory();
        
        System.out.println("Уровень: " + count + ", Память: " + usedMemory);
        
        if (count < 1000) {
            recursion(count + 1);
        }
    }
    
    public static void main(String[] args) {
        try {
            recursion(0);
        } catch (StackOverflowError e) {
            System.out.println("Переполнение стека на уровне ~" + e.getStackTrace().length);
        }
    }
}

Оптимизация хвостовой рекурсии

Некоторые языки оптимизируют хвостовую рекурсию (tail recursion), но Java этого не делает:

// Хвостовая рекурсия (Java НЕ оптимизирует)
public static long factorial(long n, long accumulator) {
    if (n == 1) {
        return accumulator; // Хвостовой вызов
    }
    return factorial(n - 1, n * accumulator); // Хвостовой вызов
}

// Java все равно будет накапливать стек!
// Решение: использовать loop
public static long factorialLoop(long n) {
    long result = 1;
    for (long i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Таблица: Правильная vs Неправильная рекурсия

Вывод

Неуправляемая рекурсия приводит к переполнению стека (StackOverflowError), когда методы вызывают друг друга без условия выхода. Для предотвращения:

1. Всегда добавляйте base case (условие выхода)
2. Убедитесь, что base case достижима (логика приводит к нему)
3. Контролируйте глубину рекурсии (не слишком глубоко)
4. Рассмотрите итеративные решения для глубокой рекурсии
5. Тестируйте с экстремальными значениями

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