Что такое рекурсия?

Рекурсия в Java

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

Основные принципы рекурсии

Любой рекурсивный алгоритм должен содержать:

1. Базовый случай — условие, при котором функция прекращает вызывать саму себя и возвращает результат
2. Рекурсивный случай — вызов функции с изменёнными параметрами, приближающимися к базовому случаю

Без базового случая функция вызывает себя бесконечно, что приводит к переполнению стека вызовов (StackOverflowError).

Простой пример: факториал

// Рекурсивное вычисление факториала
public class RecursionExample {
    public static int factorial(int n) {
        // Базовый случай
        if (n <= 1) {
            return 1;
        }
        // Рекурсивный случай
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println(factorial(5));  // Output: 120
        // Вычисление: 5 * 4 * 3 * 2 * 1 = 120
    }
}

Пример: Сумма чисел от 1 до N

public class SumRecursion {
    // Рекурсивный метод
    public static int sum(int n) {
        if (n <= 0) {
            return 0;  // Базовый случай
        }
        return n + sum(n - 1);  // Рекурсивный случай
    }
    
    public static void main(String[] args) {
        System.out.println(sum(5));  // Output: 15 (1+2+3+4+5)
    }
}

Пример: Поиск в бинарном дереве

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

public class TreeSearch {
    // Рекурсивный поиск в бинарном дереве
    public static boolean search(TreeNode node, int target) {
        // Базовый случай: узел не существует
        if (node == null) {
            return false;
        }
        
        // Найдено значение
        if (node.value == target) {
            return true;
        }
        
        // Рекурсивный поиск в левом и правом поддеревьях
        return search(node.left, target) || search(node.right, target);
    }
}

Пример: Обход файловой системы

import java.io.File;

public class FileSystemRecursion {
    public static void listFiles(String path, int depth) {
        File file = new File(path);
        
        if (!file.exists()) {
            return;  // Базовый случай
        }
        
        // Вывод текущего файла с отступом
        String indent = "  ".repeat(depth);
        System.out.println(indent + file.getName());
        
        // Если это директория, рекурсивно перейдём в неё
        if (file.isDirectory()) {
            File[] files = file.listFiles();
            if (files != null) {
                for (File f : files) {
                    listFiles(f.getAbsolutePath(), depth + 1);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        listFiles(".", 0);
    }
}

Пример: Последовательность Фибоначчи

public class FibonacciRecursion {
    // Простая рекурсивная реализация (неэффективная)
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;  // Базовый случай
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // Рекурсивный случай
    }
    
    // Оптимизированная версия с мемоизацией
    public static int fibonacciMemo(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        
        if (memo[n] != -1) {
            return memo[n];  // Возврат сохранённого результата
        }
        
        memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
        return memo[n];
    }
    
    public static void main(String[] args) {
        System.out.println(fibonacci(10));  // Output: 55
        
        // Оптимизированная версия
        int[] memo = new int[11];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = -1;
        }
        System.out.println(fibonacciMemo(10, memo));  // Output: 55 (быстрее)
    }
}

Типы рекурсии

Линейная рекурсия — функция вызывает саму себя один раз:

public static int linear(int n) {
    if (n <= 0) return 0;
    return n + linear(n - 1);
}

Двойная рекурсия — функция вызывает саму себя два раза:

public static int tree(int n) {
    if (n <= 0) return 0;
    return tree(n - 1) + tree(n - 2);
}

Взаимная рекурсия — функция A вызывает функцию B, которая вызывает функцию A:

public static boolean isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}

public static boolean isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

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

• Код более элегантен и читаем для определённых задач (деревья, графы)
• Естественно моделирует рекурсивную структуру данных
• Упрощает решение комбинаторных задач

Недостатки рекурсии

• Потребление памяти (стек вызовов растёт с глубиной)
• Медленнее итеративного подхода при наивной реализации
• Риск переполнения стека при большой глубине
• Сложнее отлаживать

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

Если рекурсивный вызов — последнее выражение, компилятор может оптимизировать его:

public static int tailFactorial(int n, int acc) {
    if (n <= 1) {
        return acc;  // Хвостовой вызов
    }
    return tailFactorial(n - 1, n * acc);
}

Рекурсия — мощный инструмент, но её нужно использовать умело, понимая компромиссы между читаемостью и производительностью