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

Несмотря на ограничения, рекурсия остается незаменимым инструментом для задач с древовидной структурой или редукцией к подзадачам.
Иерархические структуры данных: Файловая система, 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 #практика