Раздел 7. Алгоритмы

Глава 5: Рекурсия, деревья и введение в динамическое программирование

Принцип рекурсии и её опасности

Рекурсия — это методология решения задач, при которой функция вызывает сама себя для обработки подзадачи меньшего размера. В математике это называется рекуррентным соотношением, в программировании — рекурсивным вызовом. Главная идея состоит в том, чтобы свести решение сложной проблемы к решению аналогичной, но более простой проблемы, плюс некоторый шаг объединения результатов.

Представьте задачу вычисления суммы чисел от 1 до n. Итеративный подход использует цикл с аккумулятором. Рекурсивный подход говорит: сумма от 1 до n равна n плюс сумма от 1 до n-1. Это определение ссылается на само себя, но с меньшим аргументом. Такое самоподобие лежит в основе рекурсивного мышления.


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

Любая корректная рекурсивная функция строится на двух неразрывно связанных компонентах:
Базовый случай (base case) — это условие, при котором рекурсия останавливается и функция возвращает конкретное значение без дальнейших вызовов самой себя. Это точка выхода из бесконечного цикла вызовов. Без базового случая функция будет вызывать себя вечно, пока не исчерпает системные ресурсы. Для суммы чисел от 1 до n базовым случаем является ситуация, когда n равно 0 или 1 — сумма пустого множества или одного элемента тривиальна.
Рекурсивный шаг (recursive step) — это логика, связывающая результат текущего вызова с результатом вызова функции от модифицированных аргументов. Здесь кроется математическая индукция: мы предполагаем, что функция работает корректно для меньших входных данных (индукционная гипотеза), и доказываем, что тогда она работает для текущих данных.

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

Рассмотрим классический пример вычисления факториала. Математически n! определен как произведение всех натуральных чисел от 1 до n, с дополнительным условием 0! = 1.

public class RecursionFundamentals {

    /**
     * Вычисляет факториал числа n.
     * 
     * @param n неотрицательное целое число
     * @return n!
     * @throws IllegalArgumentException если n отрицательно
     */
    public static long factorial(int n) {
        // Базовый случай: факториал 0 или 1 равен 1
        // Это математическое определение, служащее якорем рекурсии
        if (n <= 1) {
            return 1;
        }
        
        // Защита от некорректного использования
        if (n < 0) {
            throw new IllegalArgumentException("Factorial undefined for negative numbers");
        }
        
        // Рекурсивный шаг: n! = n * (n-1)!
        // Здесь мы полагаемся на то, что factorial(n-1) вернет правильный результат
        // и умножаем его на n для получения текущего значения
        return n * factorial(n - 1);
    }
}

Инвариант рекурсии — условие, которое остается истинным на каждом уровне вызовов. Для факториала это утверждение, что при вызове factorial(k) мы находимся в процессе вычисления произведения чисел от k до n, где n — исходный аргумент верхнего уровня. Поддержание инварианта гарантирует корректность результата при возврате из глубины стека.


#Java #для_новичков #beginner #algorithm #recursion

Стек вызовов: механизм жизнеобеспечения рекурсии

Чтобы понять опасности рекурсии, необходимо заглянуть под капот JVM и понять, как работает стек вызовов (call stack).

Стек вызовов — это область памяти, выделенная каждому потоку выполнения в Java. Он организован по принципу LIFO (Last In, First Out — последним пришел, первым вышел).

Каждый раз, когда метод вызывается, в стек помещается фрейм активации (stack frame), содержащий:
- Локальные переменные метода (примитивы и ссылки)
- Параметры метода
- Адрес возврата (куда передать управление после завершения метода)
- Ссылку на объект this (для нестатических методов)
- Служебную информацию для отладки (номера строк в таблице символов)

При рекурсивном вызове создается новый фрейм, который логически изолирован от предыдущего. Даже если это тот же метод с тем же именем, JVM видит его как отдельный экземпляр выполнения со своим набором локальных переменных. Это изоляция позволяет каждому уровню рекурсии работать со своими копиями данных, не мешая вышестоящим вызовам.

Размер стека вызовов ограничен. В Java по умолчанию он составляет 1 мегабайт для каждого потока (значение может варьироваться в зависимости от архитектуры и версии JVM, обычно от 256KB до 2MB). Этот размер фиксируется при создании потока и не может быть динамически расширен во время выполнения.


StackOverflowError: когда глубина превышает высоту

Если рекурсия слишком глубока, стек вызовов переполняется. JVM обнаруживает попытку записи за пределы выделенной области и выбрасывает java.lang.StackOverflowError. Это не checked exception и не unchecked runtime exception в традиционном смысле — это ошибка (Error), наследник VirtualMachineError, сигнализирующая о критическом состоянии ресурсов.

Важно понимать, что StackOverflowError — это неизлечимая в рамках текущего потока ситуация. После её возникновения стек разрушен, состояние объектов может быть неопределенным, и продолжать выполнение потока нельзя. Единственное разумное действие — завершить поток или всю программу.

Какова максимальная глубина рекурсии?

Это зависит от нескольких факторов:
- Размера стека (-Xss параметр JVM)
- Количества и размера локальных переменных в методе (чем больше данных во фрейме, тем быстрее заполнится стек)
- Архитектуры (64-битные системы имеют больший оверхед на ссылки)

Для простого метода типа факториала с одним параметром типа int глубина обычно составляет от нескольких тысяч до десятков тысяч вызовов. Например, попытка вычислить factorial(100000) практически гарантированно вызовет StackOverflowError.

public class StackDepthDemo {
    
    private static int depth = 0;
    
    public static void recursiveCall() {
        depth++;
        if (depth % 1000 == 0) {
            System.out.println("Current depth: " + depth);
        }
        recursiveCall(); // Бесконечная рекурсия без базового случая
    }
    
    public static void main(String[] args) {
        try {
            recursiveCall();
        } catch (StackOverflowError e) {
            System.err.println("Stack overflow at depth: " + depth);
            // Вывод примерно: Stack overflow at depth: 10800 (зависит от -Xss)
        }
    }
}

#Java #для_новичков #beginner #algorithm #recursion

Отсутствие Tail-Call Optimization: архитектурный долг JVM

В функциональных языках программирования (Scheme, Haskell, Scala с определенными флагами) существует механизм, называемый оптимизацией хвостовой рекурсии (Tail-Call Optimization, TCO). Он позволяет преобразовать рекурсивный вызов в цикл на уровне машинного кода, если рекурсивный вызов является последней операцией в методе (хвостовой позицией).

Рассмотрим хвостовую версию факториала:

public static long factorialTail(int n, long accumulator) {
    if (n <= 1) {
        return accumulator;
    }
    // Рекурсивный вызов — последняя операция перед return
    // Теоретически JVM могла бы освободить текущий фрейм перед вызовом
    return factorialTail(n - 1, n * accumulator);
}

В языках с TCO такой код выполнялся бы с постоянным размером стека O(1), так как каждый новый вызов переиспользовал бы фрейм предыдущего. Однако JVM не поддерживает TCO. Это архитектурное решение, связанное с необходимостью сохранения точных трасс стека для отладки, профилирования и механизма SecurityManager. Каждый вызов factorialTail создает новый фрейм, и при достаточно большом n произойдет StackOverflowError.

Последствия отсутствия TCO:
- Невозможность безопасной рекурсии для больших n: Даже правильно написанная хвостовая рекурсия не спасает от переполнения стека. Вы не можете использовать рекурсию для обработки списка из миллиона элементов, даже если алгоритмически это хвостовой вызов.
- Предпочтение итерации: В Java культуре рекурсия считается менее идиоматичной, чем в функциональных языках. Циклы while и for предпочтительны для глубоких итераций, так как они используют постоянное количество памяти O(1).
- Ручное управление стеком: Для задач, естественно выражаемых через рекурсию (обход деревьев), но требующих обработки больших глубин, Java-разработчики вынуждены использовать явный стек (класс java.util.Stack или ArrayDeque), перекладывая управление памятью из стека вызовов в кучу (heap), где ограничения гораздо мягче.
- Накладные расходы:
Каждый рекурсивный вызов требует:
Выделения фрейма в стеке
Сохранения регистров процессора
Переключения контекста выполнения
Проверок безопасности (в некоторых JVM)
Это делает рекурсию медленнее итерации даже для малых глубин, хотя разница измеряется в наносекундах.


#Java #для_новичков #beginner #algorithm #recursion

Когда рекурсия естественна: домены применения

Несмотря на ограничения, рекурсия остается незаменимым инструментом для задач с древовидной структурой или редукцией к подзадачам.
Иерархические структуры данных: Файловая система, DOM-дерево HTML, абстрактные синтаксические деревья компилятора, организационные структуры компании — все это примеры данных, где каждый узел содержит ссылки на подчиненные узлы. Рекурсивная функция может обработать текущий узел и вызвать себя для каждого потомка, естественно следуя топологии данных.

Разделение задач: Алгоритмы типа "разделяй и властвуй" (merge sort, quick sort, бинарный поиск) естественно выражаются через рекурсию. Рекурсивный шаг здесь — это применение того же алгоритма к половинам массива.
Математические определения: Функции, определенные рекуррентно (числа Фибоначчи, комбинаторика, фракталы), читаются проще в рекурсивной форме, хотя эффективная реализация часто требует мемоизации или перехода к итерации.

Рассмотрим пример обхода файловой системы — классический случай, где рекурсия проявляет свою силу:

import java.io.File;

public class FileSystemTraversal {

    /**
     * Рекурсивно подсчитывает общий размер всех файлов в директории.
     * 
     * @param directory корневая директория для анализа
     * @return суммарный размер в байтах
     */
    public static long calculateDirectorySize(File directory) {
        // Базовый случай 1: несуществующий путь
        if (!directory.exists()) {
            return 0;
        }
        
        // Базовый случай 2: это файл, а не директория
        // Возвращаем его размер, рекурсия останавливается
        if (directory.isFile()) {
            return directory.length();
        }
        
        // Базовый случай 3: пустая директория (опционально, обработается циклом)
        
        // Рекурсивный шаг: получаем список содержимого
        File[] children = directory.listFiles();
        if (children == null) {
            // Защита от null при отсутствии прав доступа
            return 0;
        }
        
        long totalSize = 0;
        // Для каждого элемента в директории вызываем себя рекурсивно
        for (File child : children) {
            // Рекурсивный вызов обрабатывает поддиректории на любую глубину
            totalSize += calculateDirectorySize(child);
        }
        
        return totalSize;
    }
}

В этом примере глубина рекурсии равна глубине вложенности директорий. Для типичной файловой системы это 10-20 уровней — безопасно для стека. Но при обработке архивов с глубокой вложенностью или символических ссылок, создающих циклы, необходима защита от бесконечной рекурсии (например, через Set посещенных путей).


Практические рекомендации по безопасной рекурсии

Анализ глубины перед реализацией: Перед написанием рекурсивного метода оцените максимальную глубину вызовов. Если данные могут содержать тысячи уровней вложенности (например, парсинг JSON с глубокой вложенностью объектов), используйте итеративный подход с явным стеком.

Проверка базового случая: Всегда убедитесь, что базовый случай достижим. Для числовых аргументов это обычно проверка на ноль или единицу. Для структур данных — проверка на null или пустоту.
Защита от циклов: При обходе графов или файловых систем с символическими ссылками используйте ThreadLocal<Set> или передавайте Set<VisitedNode> через параметры для отслеживания посещенных узлов.

Размер стека: Для специфических задач с умеренной, но значительной глубиной (например, 5000 уровней) можно увеличить размер стека через флаг -Xss2m (2 мегабайта). Однако это лечит симптом, а не причину, и не масштабируется.

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


#Java #для_новичков #beginner #algorithm #recursion

Ключевые детали реализации:
Два базовых случая: файл (возвращаем размер) и нефайл (обрабатываем детей). Операция Files.isRegularFile() требует минимальных системных вызовов и не читает весь файл в память.
Защита от null: Files.newDirectoryStream() может вернуть null или бросить исключение, если доступ запрещен.
Обработка символических ссылок: Текущая реализация следует по символическим ссылкам, что может создать циклы и StackOverflowError.

Для защиты нужно добавить Set<Path> посещенных узлов:

private static long calculateRecursiveSafe(Path currentPath, Set<Path> visited) throws IOException {
    // Проверка на цикл
    if (!visited.add(currentPath.toRealPath())) {
        System.err.println("Cycle detected, skipping: " + currentPath);
        return 0;
    }
    
    if (Files.isRegularFile(currentPath)) {
        return Files.size(currentPath);
    }
    
    long totalSize = 0;
    try (DirectoryStream<Path> stream = Files.newDirectoryStream(currentPath)) {
        for (Path child : stream) {
            totalSize += calculateRecursiveSafe(child, visited);
        }
    }
    
    // Важно: не удаляем из visited при возврате, так как путь может быть повторен через другую ссылку
    return totalSize;
}

Анализ производительности и памяти

Время: O(N), где N — общее количество файлов и каталогов. Каждый узел посещается ровно один раз.
Память (стек): O(h), где h — максимальная глубина вложенности. Для домашней директории h обычно < 50, для серверов — < 500. Безопасно для 1MB стека.
Память (куча): O(h) на множество visited, если используется защита от циклов.

Иерархия жанров библиотеки — поиск в поддереве

Представим модель библиотеки, где жанры организованы в дерево:

Литература
├── Художественная
│   ├── Фантастика
│   │   ├── Космическая
│   │   └── Альтернативная история
│   └── Детектив
└── Научная
    └── Программирование
        └── Java

Каждый узел содержит название и список поджанров.

Задача: найти все книги, относящиеся к жанру «Фантастика», включая все поджанры.

Модель данных

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class GenreNode {
    private final String name;
    private final List<GenreNode> subgenres;
    private final List<Book> books; // Книги непосредственно этого жанра
    
    public GenreNode(String name) {
        this.name = name;
        this.subgenres = new ArrayList<>();
        this.books = new ArrayList<>();
    }
    
    // Методы добавления поджанров и книг...
    public void addSubgenre(GenreNode subgenre) {
        subgenres.add(subgenre);
    }
    
    public void addBook(Book book) {
        books.add(book);
    }
    
    public String getName() {
        return name;
    }
    
    public List<GenreNode> getSubgenres() {
        return Collections.unmodifiableList(subgenres);
    }
    
    public List<Book> getBooks() {
        return Collections.unmodifiableList(books);
    }
}

class Book {
    final String title;
    final String author;
    
    Book(String title, String author) {
        this.title = title;
        this.author = author;
    }
}

#Java #для_новичков #beginner #algorithm #recursion

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

import java.util.List;
import java.util.ArrayList;

public class GenreSearchService {

    /**
     * Находит все книги в указанном жанре и его поджанрах.
     * 
     * @param root корень дерева жанров
     * @param targetGenreName имя целевого жанра
     * @return список всех книг в поддереве
     */
    public static List<Book> findAllBooksInGenre(GenreNode root, String targetGenreName) {
        if (root == null || targetGenreName == null) {
            throw new IllegalArgumentException("Parameters cannot be null");
        }
        
        List<Book> result = new ArrayList<>();
        findGenreAndCollectBooks(root, targetGenreName, result);
        return result;
    }
    
    /**
     * Рекурсивный обход с поиском целевого жанра.
     * 
     * @param current текущий узел
     * @param target имя искомого жанра
     * @param accumulator список для накопления результатов
     * @return true, если целевой жанр найден в текущем поддереве
     */
    private static boolean findGenreAndCollectBooks(GenreNode current, String target, List<Book> accumulator) {
        // Базовый случай 1: мы в целевом узле
        boolean isTarget = current.getName().equals(target);
        
        // Если нашли целевой жанр, добавляем все книги этого узла
        if (isTarget) {
            accumulator.addAll(current.getBooks());
        }
        
        // Рекурсивный шаг: обходим все поджанры
        // Даже если текущий узел не целевой, его потомки могут иметь целевой жанр
        for (GenreNode child : current.getSubgenres()) {
            boolean foundInChild = findGenreAndCollectBooks(child, target, accumulator);
            
            // Если целевой жанр найден в поддереве, добавляем книги текущего узла
            // Это зависит от бизнес-логики: если нужны ТОЛЬКО книги целевого жанра и его поджанров,
            // но не промежуточных узлов, логика меняется
            if (foundInChild) {
                accumulator.addAll(current.getBooks());
            }
        }
        
        // Возвращаем true, если целевой жанр найден в этом поддереве
        return isTarget;
    }
}

Проблема текущей реализации: Она добавляет книги промежуточных узлов, когда находит цель в поддереве. Для задачи «все книги в поддереве Фантастики» это неправильно.

Исправим:

/**
 * Версия 2: Корректный поиск всех книг в поддереве целевого жанра.
 */
public static List<Book> findAllBooksInSubtree(GenreNode root, String targetGenreName) {
    List<Book> result = new ArrayList<>();
    GenreNode targetNode = findNode(root, targetGenreName);
    if (targetNode != null) {
        collectAllBooksInSubtree(targetNode, result);
    }
    return result;
}

/**
 * Первый проход: находим целевой узел.
 */
private static GenreNode findNode(GenreNode current, String target) {
    if (current.getName().equals(target)) {
        return current;
    }
    
    for (GenreNode child : current.getSubgenres()) {
        GenreNode found = findNode(child, target);
        if (found != null) {
            return found; // Остановка при первом нахождении
        }
    }
    
    return null;
}

/**
 * Второй проход: собираем все книги в поддереве.
 */
private static void collectAllBooksInSubtree(GenreNode current, List<Book> accumulator) {
    accumulator.addAll(current.getBooks());
    
    for (GenreNode child : current.getSubgenres()) {
        collectAllBooksInSubtree(child, accumulator);
    }
}

#Java #для_новичков #beginner #algorithm #recursion

Оптимизация одним проходом:

Можно совместить поиск и сбор:

private static boolean collectIfTarget(GenreNode current, String target, List<Book> accumulator) {
    // Проверяем, является ли текущий узел целевым
    boolean isTargetNode = current.getName().equals(target);
    
    // Если мы уже внутри целевого поддерева (аккумулятор в режиме сбора)...
    // Или если текущий узел — цель, начинаем сбор
    if (isTargetNode || (accumulator.size() > 0 && accumulator.get(accumulator.size() - 1) == null)) {
        accumulator.addAll(current.getBooks());
    }
    
    // Рекурсивно обходим детей
    for (GenreNode child : current.getSubgenres()) {
        collectIfTarget(child, target, accumulator);
    }
    
    return isTargetNode;
}

Эта версия сложнее для понимания. Лучше разделить ответственности: отдельно поиск, отдельно сбор.


Анализ сложности

Время: O(N), где N — общее количество узлов. В худшем случае ищем до самого последнего узла.
Память (стек): O(h), где h — высота дерева. Для сбалансированного дерева h = log N, для вырожденного (списка) h = N.

Сравнение рекурсивного и итеративного обхода

Итеративная версия с явным стеком

import java.util.ArrayDeque;
import java.util.Deque;

public class IterativeTreeTraversal {

    /**
     * Итеративный подсчет размера каталога с использованием ArrayDeque.
     * Использует кучу (heap) вместо стека вызовов.
     */
    public static long calculateSizeIterative(Path rootPath) throws IOException {
        if (!Files.isDirectory(rootPath)) {
            return Files.size(rootPath);
        }
        
        long totalSize = 0;
        Deque<Path> stack = new ArrayDeque<>();
        stack.push(rootPath);
        
        while (!stack.isEmpty()) {
            Path current = stack.pop();
            
            // Если это файл, добавляем размер
            if (Files.isRegularFile(current)) {
                totalSize += Files.size(current);
                continue;
            }
            
            // Если это директория, добавляем всех детей в стек
            try (DirectoryStream<Path> stream = Files.newDirectoryStream(current)) {
                for (Path child : stream) {
                    stack.push(child);
                }
            } catch (IOException e) {
                System.err.println("Error reading " + current + ": " + e.getMessage());
            }
        }
        
        return totalSize;
    }
    
    /**
     * Итеративный поиск книг в поддереве жанров.
     */
    public static List<Book> findBooksIterative(GenreNode root, String targetGenre) {
        List<Book> result = new ArrayList<>();
        
        // Находим целевой узел
        GenreNode targetNode = null;
        Deque<GenreNode> nodeStack = new ArrayDeque<>();
        nodeStack.push(root);
        
        while (!nodeStack.isEmpty() && targetNode == null) {
            GenreNode current = nodeStack.pop();
            
            if (current.getName().equals(targetGenre)) {
                targetNode = current;
                break;
            }
            
            // Добавляем детей в порядке обратном, чтобы обходить в исходном порядке
            List<GenreNode> children = current.getSubgenres();
            for (int i = children.size() - 1; i >= 0; i--) {
                nodeStack.push(children.get(i));
            }
        }
        
        if (targetNode == null) {
            return result;
        }
        
        // Собираем все книги в поддереве
        nodeStack.clear();
        nodeStack.push(targetNode);
        
        while (!nodeStack.isEmpty()) {
            GenreNode current = nodeStack.pop();
            result.addAll(current.getBooks());
            
            // Добавляем всех детей
            for (GenreNode child : current.getSubgenres()) {
                nodeStack.push(child);
            }
        }
        
        return result;
    }
}

#Java #для_новичков #beginner #algorithm #recursion

Сравнительный анализ

Читаемость и поддерживаемость:
Рекурсия: Естественно отражает структуру дерева. Код короче, интуитивно понятен. Подходит для алгоритмов с разделением задач (divide-and-conquer).
Итерация: Требует ручного управления стеком. Легче допустить ошибку в порядке обхода. Однако в Java культуре итерация часто считается более «идиоматичной» из-за отсутствия TCO.

Производительность:
Скорость: Рекурсия медленнее на 5-15% из-за накладных расходов на создание фреймов, проверку безопасности, сохранение регистров. Итерация работает как цикл while.
Локальность: Рекурсия хуже кэшируется, так как фреймы разбросаны в памяти. Итерация с ArrayDeque использует непрерывный массив с высокой локальностью.
Вызовы: Каждый рекурсивный вызов — это отдельный invocation в профилировщике. При больших N это замедляет JIT-компиляцию.

Память:
Рекурсия: O(h) в стеке вызовов (ограниченный ресурс). Каждый фрейм занимает 32-128 байт в зависимости от аргументов и локальных переменных.
Итерация: O(h) в куче (heap), где ограничений практически нет. ArrayDeque может расти до Integer.MAX_VALUE элементов. Один элемент стека — Path или GenreNode — занимает 8 байт для ссылки + размер объекта.

Надежность:
Стековерфлов: Рекурсия может упасть с StackOverflowError на глубине 1000-10000. Итерация не имеет этого ограничения.
Ошибки доступа: В рекурсии ошибка в одной ветви прерывает весь обход. В итерации легче продолжить после ошибки.

Параллелизм:
Рекурсия: Сложно распараллелить, так как каждый поток имеет свой стек вызовов. Нужно вручную создавать задачи для ForkJoinPool.
Итерация: Легко разделить работу между потоками, разбив стек на части.


#Java #для_новичков #beginner #algorithm #recursion

Раздел 7. Алгоритмы

Глава 5: Рекурсия, деревья и введение в динамическое программирование

От рекурсии к динамическому программированию

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

Числа Фибоначчи определяются простейшей рекуррентной формулой: F(0) = 0, F(1) = 1, а для n > 1 выполняется F(n) = F(n-1) + F(n-2). Это определение так и просится быть преобразованным в рекурсивную функцию. Однако наивная реализация скрывает в себе экспоненциальную бомбу. Мы разберем, почему это происходит, как мемоизация превращает катастрофу в триумф, и как эти идеи ложатся в основу парадигмы динамического программирования.


Наивная рекурсия и экспоненциальная сложность

Вот как выглядит буквальная имплементация определения Фибоначчи:

public class NaiveFibonacci {

    /**
     * Вычисляет n-е число Фибоначчи наивной рекурсией.
     * 
     * @param n порядковый номер, начиная с 0 (F(0)=0, F(1)=1)
     * @return n-е число Фибоначчи
     * @throws IllegalArgumentException если n отрицательный
     */
    public static long fibonacci(int n) {
        // Базовые случаи, соответствующие математическому определению
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        // Рекурсивный шаг: F(n) = F(n-1) + F(n-2)
        // Ключевой момент: два вызова на каждом уровне
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Код выглядит правильно, компилируется и дает правильные результаты для малых n. Но попробуйте вызвать fibonacci(50) и приготовьтесь ждать. Не секунды, а минуты. А fibonacci(100) на обычном железе не завершится за разумное время.

Дерево вызовов: визуализация катастрофы

Чтобы понять, почему это происходит, нужно построить дерево вызовов.

Для fibonacci(5) оно выглядит так:

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1) = 1
│   │   │   └── fibonacci(0) = 0
│   │   ├── fibonacci(1) = 1
│   │   └── 1 + 1 = 2
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) = 1
│   │   └── fibonacci(0) = 0
│   └── 2 + 1 = 3
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) = 1
│   │   └── fibonacci(0) = 0
│   ├── fibonacci(1) = 1
│   └── 1 + 1 = 2
└── 3 + 2 = 5

Заметьте: fibonacci(2) вычисляется три раза, fibonacci(3) — дважды. При увеличении n это дублирование становится катастрофическим. Дерево вызовов — не дерево, а граф, где один и тот же узел достигается множеством путей. Но наивная рекурсия это не знает и вычисляет повторно каждый раз.


Математический анализ сложности: O(2ⁿ)

Количество вызовов функции можно описать рекуррентным соотношением T(n) = T(n-1) + T(n-2) + O(1), что очень похоже на саму последовательность Фибоначчи. Можно доказать индукцией, что T(n) ≥ F(n). А поскольку F(n) ≈ φⁿ / √5, где φ ≈ 1.618 — золотое сечение, получаем экспоненциальный рост.

Более грубая, но наглядная оценка: пусть каждый вызов порождает два новых. Тогда на глубине n будет не более 2ⁿ узлов. Действительное число вызовов немного меньше из-за сокращения базовых случаев, но порядок остается экспоненциальным — O(2ⁿ).

Практические измерения (на JVM с отключенным JIT для чистоты эксперимента):
fibonacci(30) — ~2.7 миллиона вызовов, ~10 мс
fibonacci(40) — ~3.3 миллиарда вызовов, ~1000 мс
fibonacci(50) — ~4.1 триллионов вызовов, ~120 секунд
fibonacci(100) — вызовов больше, чем атомов на Земле

Это не медленный алгоритм — это неработающий алгоритм. Любая задача, где n может быть 50 или больше, становится неприемлемой.


#Java #для_новичков #beginner #algorithm #recursion

Мемоизация — кэширование как спасение

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

Идея проста: перед вычислением проверяем, есть ли результат в кэше. Если есть — возвращаем его. Если нет — вычисляем, кэшируем, возвращаем.

Реализация наивной мемоизации через HashMap

import java.util.HashMap;
import java.util.Map;

public class MemoizedFibonacci {

    // Кэш для хранения вычисленных значений. Map<аргумент, результат>
    // Используем long для n, т.к. int может переполниться при больших значениях
    private static final Map<Long, Long> memo = new HashMap<>();
    
    // Инициализация базовых случаев в кэше
    static {
        memo.put(0L, 0L);
        memo.put(1L, 1L);
    }
    
    /**
     * Потоко-НЕБЕЗОПАСНАЯ версия. Для многопоточности использовать ConcurrentHashMap.
     */
    public static long fibonacci(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        
        // Проверка кэша: если значение уже вычислено, возвращаем мгновенно
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Рекурсивный шаг с мемоизацией
        // Вычисляем только один раз, результат сохраняется в memo
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        
        // Сохраняем в кэш перед возвратом
        memo.put(n, result);
        
        return result;
    }
    
    /**
     * Метод для сброса кэша в тестах. В продакшене так делать не стоит.
     */
    public static void clearCache() {
        memo.clear();
        memo.put(0L, 0L);
        memo.put(1L, 1L);
    }
}

Что изменилось в дереве вызовов?

При fibonacci(5) первый вызов вычислит все подзначения от 0 до 5 и сохранит их в memo. Последующие вызовы из глубины рекурсии не пойдут дальше одного уровня, так как fibonacci(3) уже в кэше. Дерево вызовов превращается в прямолинейный граф с N узлов.

Анализ сложности:
Время: O(n). Каждое значение от 0 до n вычисляется ровно один раз. Всего n+1 вычислений, каждое — O(1).
Память: O(n) на кэш + O(h) на стек вызовов. Для Фибоначчи h = n в худшем случае, так что суммарно O(n). Но теперь память расходуется в куче (heap), где ограничения гораздо мягче стека.

На практике fibonacci(100) выполняется за < 1 мс, а fibonacci(1000) — за несколько микросекунд, хотя результат уже не помещается в long (можно использовать BigInteger).


Потоковая безопасность и жизненный цикл кэша

В примере выше memo — это статическое поле, общее для всех вызовов.

Это создает несколько проблем:
Потоконебезопасность: Одновременный вызов из двух потоков может повредить HashMap. Решение: ConcurrentHashMap или ThreadLocal<Map>.
Утечка памяти: Кэш живет вечно, захватывая память. Решение: использовать WeakHashMap или явный Cache из библиотеки (Caffeine, Guava).
Тестируемость: Тесты влияют друг на друга через общий кэш. Решение: инстанцировать кэш вне метода и передавать как параметр ( dependency injection).

Правильный production-ready подход:

public class FibonacciService {
    private final Map<Long, Long> memo = new ConcurrentHashMap<>();
    
    public FibonacciService() {
        memo.put(0L, 0L);
        memo.put(1L, 1L);
    }
    
    public long fibonacci(long n) {
        // computeIfAbsent — атомарная операция, потокобезопасная
        return memo.computeIfAbsent(n, key -> fibonacci(key - 1) + fibonacci(key - 2));
    }
}

#Java #для_новичков #beginner #algorithm #recursion

Динамическое программирование сверху вниз

Мемоизация — это техника.

Динамическое программирование (Dynamic Programming, DP) — это парадигма решения задач оптимизации, основанная на двух принципах:
Оптимальная подструктура: Оптимальное решение задачи содержит в себе оптимальные решения подзадач. Для Фибоначчи: F(n) оптимально вычисляется через оптимальные F(n-1) и F(n-2).
Перекрывающиеся подзадачи: Разные подзадачи содержат одни и те же еще более мелкие подзадачи. Фибоначчи — идеальный пример: F(n-1) и F(n-2) оба нуждаются в F(n-3).

Top-down DP (сверху вниз) — это именно рекурсия с мемоизацией. Мы начинаем с верхней задачи и по мере погружения кэшируем результаты.

Инвариант динамического программирования

В любом DP-алгоритме существует таблица состояний (state table). В мемоизированной версии это Map. Важно правильно определить ключ состояния — минимальный набор параметров, однозначно определяющих подзадачу. Для Фибоначчи это просто n. Для более сложных задач это может быть кортеж параметров.

Bottom-up подход: альтернатива top-down

Есть и другой способ DP — bottom-up (снизу вверх).

Мы не рекурсивно спускаемся, а итеративно строим таблицу от базовых случаев к цели:

public static long fibonacciBottomUp(long n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    long[] dp = new long[(int)n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[(int)n];
}

Для Фибоначчи можно сжать память до O(1), храня только два последних значения:

public static long fibonacciOptimized(long n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n == 0) return 0;
    
    long a = 0, b = 1;
    for (long i = 2; i <= n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

Это уже не DP, а простая математическая оптимизация, но она показывает, что DP — промежуточный этап от наивной рекурсии к оптимальному решению.


Практические применения DP в библиотечных системах

Задача: оптимальное размещение книг на полках

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

/**
 * Динамическое программирование для оптимального размещения.
 * 
 * Состояние: dp[i][w] = минимальное незаполненное пространство
 * после размещения первых i книг на полках общей ширины w.
 */
public class ShelfOptimizer {
    
    public static int optimize(List<Integer> bookThicknesses, int shelfWidth) {
        int n = bookThicknesses.size();
        int[][] dp = new int[n + 1][shelfWidth + 1];
        
        // Инициализация
        for (int w = 0; w <= shelfWidth; w++) {
            dp[0][w] = w; // Без книг осталось все свободное пространство
        }
        
        // Заполнение таблицы
        for (int i = 1; i <= n; i++) {
            int thickness = bookThicknesses.get(i - 1);
            for (int w = 0; w <= shelfWidth; w++) {
                if (thickness > w) {
                    // Книга не помещается — переносим предыдущее состояние
                    dp[i][w] = dp[i - 1][w];
                } else {
                    // Выбираем лучшее: либо не кладем книгу, либо кладем
                    dp[i][w] = Math.min(
                        dp[i - 1][w], // Не кладем
                        dp[i - 1][w - thickness] // Кладем, освобождаем оставшееся место
                    );
                }
            }
        }
        
        return dp[n][shelfWidth];
    }
}

Это классический bottom-up DP: строим таблицу, каждая ячейка определяется предыдущими.

#Java #для_новичков #beginner #algorithm #recursion

Поиск кратчайшего пути в графе книг

Если книги связаны рекомендациями «после прочтения этой, читайте эту», можно найти кратчайшую цепочку от книги A до книги B через DP:

/**
 * Определение длины кратчайшего пути от start до end.
 * dp[v] = минимальная длина пути от start до v.
 */
public static int shortestPathLength(Map<String, List<String>> graph, String start, String end) {
    Map<String, Integer> dp = new HashMap<>();
    dp.put(start, 0);
    
    // BFS + DP гибрид
    Queue<String> queue = new ArrayDeque<>();
    queue.add(start);
    
    while (!queue.isEmpty()) {
        String current = queue.poll();
        int currentDist = dp.get(current);
        
        if (current.equals(end)) {
            return currentDist;
        }
        
        for (String neighbor : graph.getOrDefault(current, List.of())) {
            if (!dp.containsKey(neighbor) || dp.get(neighbor) > currentDist + 1) {
                dp.put(neighbor, currentDist + 1);
                queue.add(neighbor);
            }
        }
    }
    
    return -1; // Путь не найден
}

Это пример DP, где состояние — это вершина графа.

Подводные камни и best practices

1. Выбор ключа состояния
Ключ должен быть минимальным и однозначным. Для задачи «подсчет путей в сетке» ключ — это (x, y). Для задачи «редактирование строки» — (i, j), где i и j — позиции в строках. Если ключ слишком большой (содержит лишние поля), кэш раздувается. Если неоднозначный — получите неверные результаты.

2. Порядок вычислений и рекурсивные циклы
Если подзадачи зависят друг от друга (например, в графе с циклами), naive top-down DP может зациклиться. Решение:
Добавить состояние "в процессе" в кэш и бросать исключение при повторном входе
Использовать bottom-up
Применять алгоритмы для графов с циклами (topological sort)

3. Память vs время
DP всегда торгует памятью на время. Для задач с большим количеством состояний (например, dp[1000][1000][1000]) память может стать bottlenek'ом. Тогда применяют:
Оптимизацию памяти: хранить только нужные строки таблицы
Встречный поиск (meet-in-the-middle): разбить задачу на две половины
Аппроксимацию: отказаться от точного DP в пользу эвристик

4. Не всё можно решить DP
DP требует оптимальной подструктуры и перекрывающихся подзадач. Если решение задачи не складывается из решений подзадач (например, задача о ранце с взаимозависимыми вещами), DP неприменим.

5. Состояние гонки в мемоизации
В многопоточной среде используйте ConcurrentHashMap.computeIfAbsent, который атомарно вычисляет значение, если его нет. Но будьте осторожны: рекурсивный вызов внутри лямбды может заблокировать bucket и вызвать deadlock при рекурсивных зависимостях.

Раздел 6: От DP к современным практикам
Кэширование в распределенных системах
В микросервисах, управляющих библиотекой, DP-подход применяется через распределенный кэш (Redis, Memcached). Состояние — ключ в Redis, рекурсия — это серийный вызов сервисов. Но теперь нужно думать о сетевых задержках, а не только о процессоре.
Машинное обучение и DP
В NLP для разбора предложений используется CYK-алгоритм — DP по грамматике. В компьютерном зрении для выравнивания изображений — динамическое искажение времени (DTW). DP — фундаментальная парадигма не только в классических алгоритмах.

#Java #для_новичков #beginner #algorithm #recursion

Раздел 7. Алгоритмы

Глава 5: Рекурсия, деревья и введение в динамическое программирование

Практическое применение рекурсии в библиотечной системе

Цели:
Освоить принципы работы с древовидными структурами
Научиться применять рекурсию для обхода иерархических данных
Сравнить рекурсивные и итеративные подходы
Понять оптимизацию рекурсии через мемоизацию


Часть 1: Моделирование древовидной структуры жанров

Постановка задачи:
В нашей библиотеке жанры книг образуют иерархию.

Например:
Литература (корень)
Художественная литература
Фантастика
Научная фантастика
Фэнтези
Нехудожественная литература

Вам нужно: Создать структуру данных, которая позволит хранить такую иерархию.

Шаг 1.1: Создайте класс Genre

Что нужно сделать:

Определите, какие поля понадобятся для хранения:
Название жанра
Список поджанров (дочерние элементы)
Список книг, относящихся к этому жанру

Реализуйте:
Конструктор, принимающий название жанра
Методы для добавления поджанра и книги
Геттеры для доступа к данным

Вопрос для размышления: Почему важно, чтобы поджанры хранились как список объектов Genre?

Шаг 1.2: Свяжите книги с жанрами

Что нужно сделать:

Обновите класс Book:
Добавьте поле для хранения основного жанра книги
Измените конструктор для установки жанра

Подумайте: Может ли книга принадлежать к нескольким жанрам? Как это реализовать?

Шаг 1.3: Построение дерева жанров

Практическое задание:

В классе Library создайте метод initGenres(), который:
Создаёт корневой жанр "Литература"
Добавляет 3-4 уровня вложенности жанров
Распределяет существующие книги по соответствующим жанрам

Проверка: Убедитесь, что у вас получилось дерево глубиной не менее 4 уровней.


Часть 2: Рекурсивный подсчёт книг в жанре

Задача: Напишите метод, который считает все книги в жанре и его поджанрах

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

Пример:

Книг в "Фантастике" = 
  книги в "Фантастике" + 
  книги в "Научной фантастике" + 
  книги в "Фэнтези"

Шаг 2.1: Реализуйте метод countBooksRecursive()

Что нужно сделать:
Добавьте метод в класс Genre
Реализуйте рекурсивный подсчёт по описанному алгоритму
Протестируйте на разных уровнях дерева

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


Часть 3: Сравнение рекурсивного и итеративного обхода

Задача: Вывести структуру дерева жанров двумя способами

Шаг 3.1: Рекурсивный обход (Pre-order)

Алгоритм:
Обработать текущий узел (вывести информацию)
Рекурсивно обработать все дочерние узлы

Что нужно сделать:
Реализуйте метод printTreeRecursive(Genre genre, int depth), где depth используется для создания отступов при выводе.

Шаг 3.2: Итеративный обход с использованием стека

Можно эмулировать рекурсию с помощью стека:
Помещаем корневой элемент в стек

Пока стек не пуст:
Извлекаем элемент
Обрабатываем его
Добавляем в стек его детей

Что нужно сделать:
Реализуйте метод printTreeIterative(Genre root) с использованием Stack<Genre>.

Вопрос: Почему детей нужно добавлять в стек в обратном порядке?

Шаг 3.3: Сравнение подходов

Практическое задание:
Создайте дерево глубиной 10 уровней
Замерьте время выполнения обоих методов

Ответьте на вопросы:
Какой подход читаемее?
Какой безопаснее для глубоких деревьев?
Когда стоит использовать каждый из них?


#Java #для_новичков #beginner #algorithm #recursion #практика

Часть 4: Числа Фибоначчи - три подхода

Задача: Вычислить n-ное число Фибоначчи

Определение:
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

Шаг 4.1: Наивная рекурсия

Что нужно сделать:
Реализуйте метод fibRecursive(int n) по определению.

Анализ проблемы:
Нарисуйте дерево вызовов для n=5. Сколько раз вычисляется F(2)? F(3)?

Задание: Замерьте время выполнения для n=40. Почему это так долго?

Шаг 4.2: Мемоизация (Top-down динамическое программирование)

Идея: Сохранять уже вычисленные значения, чтобы не вычислять их повторно.

Что нужно сделать:
Создайте HashMap<Integer, Long> для хранения вычисленных значений

Измените рекурсивную функцию так, чтобы она:
Проверяла, нет ли значения в кэше
Сохраняла новое значение после вычисления

Вопрос: Как изменилось дерево вызовов?

Шаг 4.3: Итеративное решение (Bottom-up)

Алгоритм:
Если n <= 1: вернуть n
Иначе: последовательно вычислить все числа от 2 до n

Что нужно сделать:
Реализуйте метод fibIterative(int n) без рекурсии.

Задание: Сравните производительность всех трёх методов для n=50.


Итоговые задания

Задание 1: Рефакторинг
Перепишите один из рекурсивных методов в итеративный. Объясните, что изменилось в сложности кода.

Задание 2: Оптимизация
Добавьте проверку на циклические ссылки в дереве жанров. Что произойдёт без этой проверки?

Задание 3: Эксперимент
Создайте глубокое дерево (20+ уровней). Протестируйте оба метода обхода. При какой глубине возникает StackOverflowError?

Задание 4: Документация

Напишите комментарии к методам, объясняющие:
Сложность алгоритма (Big O)
Ограничения (максимальная глубина)
Рекомендации по использованию


#Java #для_новичков #beginner #algorithm #recursion #практика