Что такое рекурсия? Когда использовать?

Рекурсия - вызов функцией самой себя:

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

// Обход дерева - классический случай для рекурсии
function flatten(array $arr): array {
    $result = [];
    foreach ($arr as $item) {
        if (is_array($item)) {
            $result = array_merge($result, flatten($item));
        } else {
            $result[] = $item;
        }
    }
    return $result;
}

Используйте для: обхода деревьев, фракталов, divide-and-conquer. Избегайте для линейных задач (используйте циклы). PHP не оптимизирует хвостовую рекурсию, глубокая рекурсия может вызвать stack overflow.