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

Функция, вызывающая саму себя.

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

Пример вычисления факториала:

<?php
function factorial(int $n): int
{
    // Базовый случай
    if ($n <= 1) {
        return 1;
    }
    // Рекурсивный вызов
    return $n * factorial($n - 1);
}

echo factorial(5); // Выведет 120
?>

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

• Элегантность и лаконичность кода для определенных задач.

Недостатки:

• Может привести к переполнению стека при слишком глубоком уровне вложенности.
• Потенциально менее производительна, чем итерационные решения для тех же задач из-за накладных расходов на вызовы функций.

Часто применяется для обхода деревьев, файловых систем, решения комбинаторных задач.