Что такое рекурсия в программировании?

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

Ключевые компоненты рекурсивной функции:

1. Базовый случай (терминальный случай): Простое условие, при котором функция возвращает результат без дальнейших рекурсивных вызовов. Обязателен для предотвращения бесконечной рекурсии и переполнения стека вызовов.
2. Рекурсивный шаг: Вызов функции самой себя с изменёнными (обычно упрощёнными) аргументами, которые приближают задачу к базовому случаю.

Классический пример: вычисление факториала. n! = n * (n-1)!, где 0! = 1 (базовый случай).

function factorial(int $n): int {
    // 1. Базовый случай
    if ($n <= 1) {
        return 1;
    }
    // 2. Рекурсивный шаг: задача сводится к меньшей (n-1)
    return $n * factorial($n - 1);
}

echo factorial(5); // 120
// Вызовы: factorial(5) -> 5 * factorial(4)
//                   -> 5 * (4 * factorial(3))
//                   -> 5 * (4 * (3 * factorial(2)))
//                   -> 5 * (4 * (3 * (2 * factorial(1))))
//                   -> 5 * (4 * (3 * (2 * 1))) = 120

Более практический пример: обход дерева каталогов.

function listFilesRecursively(string $directory): void {
    $items = scandir($directory);

    foreach ($items as $item) {
        if ($item === '.' || $item === '..') {
            continue; // Пропускаем служебные записи
        }

        $path = $directory . DIRECTORY_SEPARATOR . $item;

        if (is_dir($path)) {
            // Рекурсивный шаг: зашли в подкаталог
            echo "Каталог: $pathn";
            listFilesRecursively($path);
        } else {
            // Базовый "случай" для этого уровня рекурсии — это файл
            echo "  Файл: $itemn";
        }
    }
}

listFilesRecursively('/path/to/project');

Плюсы рекурсии:

• Элегантность и читаемость для задач, имеющих рекурсивную природу (обход деревьев, графов, синтаксический разбор, задачи типа "Ханойские башни", "Фибоначчи").
• Позволяет писать компактный код для сложных вложенных структур.

Минусы и ограничения:

• Потребление памяти: Каждый рекурсивный вызов помещает новый контекст выполнения в стек. При большой глубине рекурсии это может привести к переполнению стека (Stack Overflow).
• Производительность: Часто проигрывает итеративным решениям из-за накладных расходов на вызовы функций.

Когда использовать: Когда задача естественным образом разбивается на идентичные подзадачи (разделяй и властвуй), и глубина рекурсии гарантированно невелика или контролируема. В иных случаях часто предпочтительнее итерация с использованием циклов и явных структур данных (например, стека).