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

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)
        }
    }
}

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

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

public class Task280126 {
    public static void main(String[] args) {

        System.out.println(f(7));

    }

    static int f(int n) {

        if (n <= 1) return 1;
        return f(n - 2) + f(n - 1);

    }
}

import java.io.IOException;
import java.nio.file.*;
import java.nio.file.attribute.BasicFileAttributes;

public class FileSizeCalculator {

    /**
     * Вычисляет общий размер всех файлов в каталоге и его подкаталогах.
     * 
     * @param rootPath корневой каталог для анализа
     * @return суммарный размер в байтах
     * @throws IllegalArgumentException если rootPath не является каталогом или не существует
     */
    public static long calculateSize(Path rootPath) {
        if (rootPath == null) {
            throw new IllegalArgumentException("Path cannot be null");
        }
        
        // Проверяем существование и тип файловой системы
        if (!Files.exists(rootPath)) {
            throw new IllegalArgumentException("Path does not exist: " + rootPath);
        }
        
        if (!Files.isDirectory(rootPath)) {
            throw new IllegalArgumentException("Path is not a directory: " + rootPath);
        }
        
        try {
            return calculateRecursive(rootPath);
        } catch (IOException e) {
            // Преобразуем checked exception в unchecked для удобства API
            throw new UncheckedIOException("Failed to traverse directory: " + rootPath, e);
        }
    }
    
    /**
     * Внутренний рекурсивный метод.
     * 
     * @param currentPath текущий узел для анализа
     * @return суммарный размер поддерева
     */
    private static long calculateRecursive(Path currentPath) throws IOException {
        // Базовый случай 1: это файл
        if (Files.isRegularFile(currentPath)) {
            try {
                return Files.size(currentPath);
            } catch (SecurityException | IOException e) {
                // В реальном приложении логгируем ошибку доступа
                // и продолжаем, а не прокидываем исключение
                System.err.println("Cannot access file: " + currentPath + " - " + e.getMessage());
                return 0;
            }
        }
        
        //случай 2: это директория, обрабатываем её содержимое
        long totalSize = 0;
        
        // Используем try-with-resources для безопасного закрытия DirectoryStream
        try (DirectoryStream<Path> stream = Files.newDirectoryStream(currentPath)) {
            for (Path child : stream) {
                // Рекурсивный вызов для каждого дочернего элемента
                // Глубина рекурсии = уровень вложенности директорий
                totalSize += calculateRecursive(child);
            }
        } catch (NotDirectoryException e) {
            // Это не должно случиться из-за проверки выше, но защита от race condition
            return 0;
        } catch (SecurityException e) {
            System.err.println("Access denied to directory: " + currentPath);
            return 0;
        }
        
        return totalSize;
   }
}

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

Литература
├── Художественная
│   ├── Фантастика
│   │   ├── Космическая
│   │   └── Альтернативная история
│   └── Детектив
└── Научная
    └── Программирование
        └── 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;
    }
}

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

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

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

import java.util.*;

public class Task290126 {
    static class Node290126 {
        int value;
        Node290126 left, right;
        Node290126(int value) { this.value = value; }
    }
    
    public static void main(String[] args) {
        Node290126 root = new Node290126(1);
        root.left = new Node290126(2);
        root.right = new Node290126(3);
        root.left.left = new Node290126(4);
        root.left.right = new Node290126(5);
        root.right.left = new Node290126(6);
        root.right.right = new Node290126(7);
        
        List<Integer> result = new ArrayList<>();
        preorderTraversal(root, result);
        System.out.println(result);
    }
    
    static void preorderTraversal(Node290126 node, List<Integer> result) {
        if (node == null) return;
        result.add(node.value);
        preorderTraversal(node.left, result);
        preorderTraversal(node.right, result);
    }
}

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

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

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

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

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

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

/**
 * Определение длины кратчайшего пути от 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, где состояние — это вершина графа.