Рекурсия в Java.

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

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

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

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

Пример простой рекурсивной функции — вычисление факториала:

public class FactorialExample {
    public static int factorial(int n) {
        if (n == 0) {
            return 1; // Базовый случай
        } else {
            return n * factorial(n - 1); // Рекурсивный случай
        }
    }

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("Factorial of 5 is: " + result);
    }
}
В этом примере функция factorial вызывает саму себя, пока не достигнет базового случая, когда n равно 0.

Виды рекурсии

Прямая рекурсия (Direct Recursion)

В прямой рекурсии функция напрямую вызывает саму себя. Это самый простой и распространенный вид рекурсии.

public class DirectRecursionExample {
    public static void countdown(int n) {
        if (n == 0) {
            System.out.println("Done!");
        } else {
            System.out.println(n);
            countdown(n - 1); // Прямой рекурсивный вызов
        }
    }

    public static void main(String[] args) {
        countdown(5);
    }
}

Косвенная рекурсия (Indirect Recursion)

В косвенной рекурсии функция A вызывает функцию B, которая в свою очередь вызывает функцию A. Этот процесс может быть продолжен с участием нескольких функций, которые вызывают друг друга.

public class IndirectRecursionExample {
    public static void functionA(int n) {
        if (n > 0) {
            System.out.println("A: " + n);
            functionB(n - 1);
        }
    }

    public static void functionB(int n) {
        if (n > 0) {
            System.out.println("B: " + n);
            functionA(n - 1);
        }
    }

    public static void main(String[] args) {
        functionA(5);
    }
}

Хвостовая рекурсия (Tail Recursion)

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

public class TailRecursionExample {
    public static int tailFactorial(int n, int acc) {
        if (n == 0) {
            return acc;
        } else {
            return tailFactorial(n - 1, n * acc); // Хвостовой рекурсивный вызов
        }
    }

    public static void main(String[] args) {
        int result = tailFactorial(5, 1);
        System.out.println("Factorial of 5 is: " + result);
    }
}
В этом примере хвостовая рекурсия позволяет эффективно вычислить факториал без необходимости удерживать промежуточные результаты в стеке вызовов.

#Java #Training #Medium #Recursion

Нерегулярная рекурсия (Non-Regular Recursion)

Нерегулярная рекурсия используется в случаях, когда количество рекурсивных вызовов не фиксировано. Она часто используется для обхода графов, деревьев и других структур данных.

public class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
        left = right = null;
    }
}

public class TreeTraversal {
    public static void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left); // Рекурсивный вызов для левого поддерева
            System.out.println(node.value);
            inOrder(node.right); // Рекурсивный вызов для правого поддерева
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        inOrder(root);
    }
}
В этом примере используется нерегулярная рекурсия для обхода бинарного дерева в порядке in-order.

Внутреннее устройство рекурсии

Рекурсия в Java и других языках программирования основывается на стеке вызовов. Когда функция вызывает саму себя, текущее состояние функции (значения переменных, адрес возврата и т.д.) сохраняется в стеке вызовов. После завершения рекурсивного вызова управление возвращается к предыдущему состоянию.

Стек вызовов — это структура данных, работающая по принципу "последним пришел — первым вышел" (LIFO). Каждый рекурсивный вызов добавляет новый фрейм в стек, который содержит информацию о текущем состоянии функции. После завершения рекурсивного вызова этот фрейм удаляется из стека, и программа возвращается к предыдущему вызову.

Пример работы стека вызовов на примере вычисления факториала числа 3.

factorial(3)
  -> 3 * factorial(2)
      -> 2 * factorial(1)
          -> 1 * factorial(0)
              -> return 1
          -> return 1 * 1 = 1
      -> return 2 * 1 = 2
  -> return 3 * 2 = 6
На каждом этапе рекурсивного вызова в стек добавляется новый фрейм. Когда функция достигает базового случая (factorial(0)), она начинает возвращаться, удаляя фреймы из стека и комбинируя результаты.

Преимущества и недостатки рекурсии

Преимущества:
Простота и элегантность: Рекурсия позволяет выражать сложные задачи простым и интуитивно понятным способом, особенно для задач, которые имеют естественную рекурсивную структуру.
Минимизация кода: Рекурсивные функции могут быть короче и понятнее, чем их итеративные аналоги.
Легкость реализации: В некоторых задачах (например, обход графа) рекурсия позволяет легко реализовать алгоритм без необходимости явного использования стека или других структур данных.

Недостатки:
Риск переполнения стека: Если глубина рекурсии слишком велика, это может привести к переполнению стека вызовов и завершению программы с ошибкой StackOverflowError.
Затраты на память и производительность: Каждый рекурсивный вызов требует дополнительной памяти для хранения состояния в стеке, что может негативно сказаться на производительности программы.
Сложность отладки: Рекурсивные программы сложнее отлаживать из-за необходимости отслеживания множества уровней вызовов.

#Java #Training #Medium #Recursion

Примеры использования рекурсии в Java.

1. Вычисление чисел Фибоначчи

Одним из классических примеров рекурсии является вычисление чисел Фибоначчи. Последовательность Фибоначчи определяется следующим образом:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) для n > 1

Пример реализации:

public class FibonacciExample {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0; // Базовый случай
        } else if (n == 1) {
            return 1; // Базовый случай
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // Рекурсивный случай
        }
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
    }
}
Этот код вычисляет 10-е число Фибоначчи. Однако, такой подход неэффективен для больших значений n, так как происходит многократное вычисление одних и тех же значений. В таких случаях лучше использовать динамическое программирование или итеративные решения.

2. Обратная строка
Рекурсия может быть использована для выполнения операций на строках. Например, мы можем создать функцию, которая будет возвращать обратную строку, используя рекурсию.

public class ReverseStringExample {
    public static String reverse(String str) {
        if (str.isEmpty()) {
            return str; // Базовый случай
        }
        return reverse(str.substring(1)) + str.charAt(0); // Рекурсивный случай
    }

    public static void main(String[] args) {
        String original = "hello";
        String reversed = reverse(original);
        System.out.println("Original: " + original);
        System.out.println("Reversed: " + reversed);
    }
}
Этот код переворачивает строку "hello" и выводит "olleh". Рекурсивная функция reverse удаляет первый символ строки и добавляет его в конец результата рекурсивного вызова.

3. Поиск максимального элемента в массиве
Еще один пример применения рекурсии — поиск максимального элемента в массиве. Для этого мы можем рекурсивно сравнивать элементы массива, пока не найдем максимальный.

public class MaxElementExample {
    public static int findMax(int[] arr, int n) {
        if (n == 1) {
            return arr[0]; // Базовый случай: один элемент
        }
        return Math.max(arr[n - 1], findMax(arr, n - 1)); // Рекурсивный случай
    }

    public static void main(String[] args) {
        int[] array = {1, 5, 3, 9, 2};
        int max = findMax(array, array.length);
        System.out.println("Maximum element is: " + max);
    }
}
Этот код ищет максимальный элемент в массиве [1, 5, 3, 9, 2], и выводит 9.

4. Обход директории
Рекурсия также может быть использована для обхода файловой системы. Например, для поиска файлов в директории и всех её поддиректориях.

import java.io.File;

public class DirectoryTraversalExample {
    public static void listFiles(File dir) {
        File[] files = dir.listFiles();
        if (files != null) {
            for (File file : files) {
                if (file.isDirectory()) {
                    listFiles(file); // Рекурсивный случай: обход поддиректории
                } else {
                    System.out.println("File: " + file.getAbsolutePath());
                }
            }
        }
    }

    public static void main(String[] args) {
        File dir = new File("/path/to/directory");
        listFiles(dir);
    }
}
Этот код рекурсивно обходит директорию и все её поддиректории, выводя полные пути к файлам.

#Java #Training #Medium #Recursion

5. Разрешение головоломок
Рекурсия часто используется в решении задач и головоломок, таких как задача о восьми ферзях, судоку и другие. Например, рассмотрим задачу о Ханойской башне.

Пример реализации Ханойской башни:

public class TowerOfHanoiExample {
    public static void solveHanoi(int n, char fromRod, char toRod, char auxRod) {
        if (n == 1) {
            System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
            return;
        }
        solveHanoi(n - 1, fromRod, auxRod, toRod);
        System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
        solveHanoi(n - 1, auxRod, toRod, fromRod);
    }

    public static void main(String[] args) {
        int n = 3; // Количество дисков
        solveHanoi(n, 'A', 'C', 'B');  // A, B и C - названия стержней
    }
}
Этот код решает задачу о Ханойской башне для трех дисков. Рекурсивная функция перемещает диски между стержнями согласно правилам задачи.

6. Генерация всех перестановок строки

Рекурсия может быть использована для генерации всех возможных перестановок символов строки. Этот алгоритм полезен в задачах комбинаторики.

public class PermutationsExample {
    public static void permute(String str, int l, int r) {
        if (l == r) {
            System.out.println(str);
        } else {
            for (int i = l; i <= r; i++) {
                str = swap(str, l, i);
                permute(str, l + 1, r);
                str = swap(str, l, i); // Возврат к исходному состоянию
            }
        }
    }

    public static String swap(String str, int i, int j) {
        char[] charArray = str.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    public static void main(String[] args) {
        String str = "ABC";
        int n = str.length();
        permute(str, 0, n - 1);
    }
}
Этот код генерирует все перестановки строки "ABC" и выводит их.

#Java #Training #Medium #Recursion

Раздел 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