Рекурсия

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

Если уже работал с Go - там про рекурсию есть отдельный урок с похожими примерами. PHP-специфика здесь: ограничения стека, рекурсивные замыкания и встроенные итераторы.

Основы

Каждая рекурсивная функция должна иметь:

  1. Базовый случай - когда рекурсия останавливается
  2. Рекурсивный шаг - вызов себя с уменьшенной задачей
<?php
declare(strict_types=1);

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

echo factorial(5); // 120

Что происходит в памяти

factorial(5)
  -> 5 * factorial(4)
    -> 4 * factorial(3)
      -> 3 * factorial(2)
        -> 2 * factorial(1)
          -> 1  <- базовый случай
        <- 2 * 1 = 2
      <- 3 * 2 = 6
    <- 4 * 6 = 24
  <- 5 * 24 = 120

Каждый вызов - новый фрейм в стеке вызовов. PHP добавляет фрейм ~220-250 байт, плюс локальные переменные.

Ограничения стека в PHP

⚠️ max_nesting_level

С xdebug (расширение-отладчик PHP, обычно стоит только в dev) глубину стека ограничивает xdebug.max_nesting_level (по умолчанию 512, до Xdebug 3.3 было 256): при превышении бросается Error с текстом Xdebug has detected a possible infinite loop, and aborted your script with a stack depth of '512' frames. Без xdebug лимита глубины нет, упрёшься в memory_limit (обычно 128M): Fatal error: Allowed memory size of ... bytes exhausted. При memory_limit = -1 процесс съест память, пока его не убьёт ОС.

<?php
declare(strict_types=1);

// Проверь текущий лимит
echo ini_get('xdebug.max_nesting_level'); // 512 по умолчанию (Xdebug 3.3+)

// Поднять программно (если xdebug включён):
ini_set('xdebug.max_nesting_level', '1000');

Для обхода глубоких структур (больше 200-300 уровней) лучше использовать итеративный подход со стеком вручную.

Примеры

Числа Фибоначчи

<?php
declare(strict_types=1);

// Наивная реализация - O(2^n), экспоненциально медленно
function fib(int $n): int
{
    if ($n <= 1) {
        return $n;
    }
    return fib($n - 1) + fib($n - 2);
}

// С мемоизацией через статический массив - O(n)
function fibMemo(int $n, array &$cache = []): int
{
    if ($n <= 1) {
        return $n;
    }
    if (isset($cache[$n])) {
        return $cache[$n];
    }
    $cache[$n] = fibMemo($n - 1, $cache) + fibMemo($n - 2, $cache);
    return $cache[$n];
}

echo fibMemo(50); // быстро

Обход вложенного массива

<?php
declare(strict_types=1);

function sumNested(array $data): int
{
    $total = 0;
    foreach ($data as $item) {
        if (is_array($item)) {
            $total += sumNested($item); // рекурсия для вложенного массива
        } else {
            $total += (int) $item;
        }
    }
    return $total;
}

$data = [1, [2, 3], [4, [5, 6]]];
echo sumNested($data); // 21

PHP предоставляет встроенную array_walk_recursive() для похожих задач. Она сама спускается во вложенные массивы и вызывает callback только для «листьев» - значений, которые не массивы; сами подмассивы в callback не попадают. Нового массива функция не возвращает, поэтому результат копим во внешней переменной через use (&$total):

<?php
declare(strict_types=1);

$total = 0;
array_walk_recursive($data, static function (mixed $value) use (&$total): void {
    $total += (int) $value;
});
echo $total; // 21

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

<?php
declare(strict_types=1);

function listFiles(string $path, int $indent = 0): void
{
    $prefix = str_repeat('  ', $indent);
    foreach (scandir($path) as $entry) {
        if ($entry === '.' || $entry === '..') {
            continue;
        }
        $fullPath = $path . '/' . $entry;
        echo $prefix . $entry . "\n";
        if (is_dir($fullPath)) {
            listFiles($fullPath, $indent + 1); // рекурсия для подкаталогов
        }
    }
}

listFiles('/var/www');

PHP также предоставляет встроенный RecursiveDirectoryIterator - итерационный подход без ограничения стека:

<?php
declare(strict_types=1);

$iterator = new RecursiveIteratorIterator(
    new RecursiveDirectoryIterator('/var/www', RecursiveDirectoryIterator::SKIP_DOTS)
);

foreach ($iterator as $file) {
    echo $file->getPathname() . "\n";
}

Здесь впервые встречаются объекты - подробно они будут в уроке 14. Пока достаточно знать: new ИмяКласса(...) создаёт объект, ИмяКласса::SKIP_DOTS - константа класса (флаг «не показывать . и ..»), а $file->getPathname() - вызов метода объекта, который возвращает путь к файлу.

Бинарный поиск (рекурсивный)

<?php
declare(strict_types=1);

function binarySearch(array $sorted, int $target, int $lo, int $hi): int
{
    if ($lo > $hi) {
        return -1;
    }
    $mid = intdiv($lo + $hi, 2);
    if ($sorted[$mid] === $target) {
        return $mid;
    }
    if ($sorted[$mid] < $target) {
        return binarySearch($sorted, $target, $mid + 1, $hi);
    }
    return binarySearch($sorted, $target, $lo, $mid - 1);
}

$nums = [1, 3, 5, 7, 9, 11];
echo binarySearch($nums, 7, 0, count($nums) - 1); // 3

Рекурсивные замыкания

Именованная функция в PHP может вызвать саму себя по имени. Анонимное замыкание - нет, потому что у него нет имени. Обходится через use (&$self, ...):

<?php
declare(strict_types=1);

$factorial = static function (int $n) use (&$factorial): int {
    if ($n <= 1) {
        return 1;
    }
    return $n * $factorial($n - 1); // $factorial доступна через замыкание
};

echo $factorial(5); // 120

use (&$factorial) - обязательно по ссылке (&), потому что в момент создания замыкания переменная $factorial ещё не содержит само замыкание.

ℹ️ Symfony и рекурсия

В Symfony рекурсия встречается в DependencyInjection компоненте при обходе графа сервисов (в том числе чтобы обнаружить циклическую зависимость и бросить ServiceCircularReferenceException) и в VarDumper при обходе вложенных объектов. Аналог рекурсивного замыкания - рекурсивный метод в сервисе.

Рекурсия vs Итерация

Любую рекурсию можно переписать через цикл:

<?php
declare(strict_types=1);

// Рекурсия
function factorialRec(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    return $n * factorialRec($n - 1);
}

// Итерация - не использует стек вызовов
function factorialIter(int $n): int
{
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}
РекурсияИтерация
ЧитаемостьДля деревьев, графов - понятнееДля линейных задач - проще
ПамятьO(n) стек вызововO(1)
СкоростьOverhead на вызовы функцииОбычно быстрее
Лимиты PHPmax_nesting_level / memory_limitНет ограничений на глубину
КогдаДеревья, вложенные структуры, графыМассивы, числа, линейные задачи

ℹ️ Правило

Используй рекурсию, когда структура данных рекурсивна (дерево, граф, вложенный JSON). Для линейных задач (factorial, fibonacci) - итерация лучше и безопаснее с точки зрения стека PHP.

Типичные ошибки

<?php
declare(strict_types=1);

// ОШИБКА 1: нет базового случая
function infinite(int $n): int
{
    return $n + infinite($n - 1); // с xdebug - Error про max_nesting_level, без него - Allowed memory size exhausted
}

// ОШИБКА 2: базовый случай недостижим
function badFib(int $n): int
{
    if ($n === 0) {
        return 0;
    }
    return badFib($n - 1) + badFib($n - 2); // при n=1 уйдёт в badFib(-1) -> бесконечность
}

// ОШИБКА 3: замыкание без & у ссылки на себя
$fact = static function (int $n) use ($fact): int { // $fact - копия null!
    return $n <= 1 ? 1 : $n * $fact($n - 1);        // Fatal error
};
// Правильно: use (&$fact)

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.