Увійти Реєстрація
Вакансії
Вакансії Laravel Компанії Статистика
Підготовка
Як підготуватися Співбесіди Тестування Документація
Блог
Всі статті Серії
Екосистема
Пакети Ресурси Проєкти Інструменти Події Відео
Інше
Про нас Реклама

Які обмеження рекурсії в PHP і як обійти глибоку рекурсію?

Рекурсія - функція викликає сама себе. Природна для деревовидних даних: каталоги, коментарі з відповідями, категорії, розбір вкладеного JSON.

function totalSize(array $node): int
{
    $size = $node['size'];
    foreach ($node['children'] as $child) {
        $size += totalSize($child);
    }
    return $size;
}

Обмеження в PHP:

  • Кожен виклик займає пам'ять у стеку викликів. Глибина в десятки тисяч рівнів може вичерпати стек.
  • Немає оптимізації хвостової рекурсії: навіть return f($n - 1) наприкінці функції займає новий кадр стеку.
  • Наслідки переповнення залежать від версії й платформи. PHP 8.3 додав налаштування zend.max_allowed_stack_size, з яким рушій кидає Error «Maximum call stack size reached» замість падіння. Але на частині конфігурацій процес усе одно аварійно завершується (segfault) без жодного стек-трейсу. З Xdebug діє власний ліміт xdebug.max_nesting_level.

Як обійти глибоку рекурсію - ітерацією з явним стеком:

function totalSize(array $root): int
{
    $size = 0;
    $stack = [$root];

    while ($stack !== []) {
        $node = array_pop($stack);
        $size += $node['size'];
        foreach ($node['children'] as $child) {
            $stack[] = $child;
        }
    }

    return $size;
}

Стек тепер - звичайний масив у купі, обмежений лише memory_limit.

Інші варіанти:

  • Генератори з yield from - обхід дерева без накопичення результатів у пам'яті.
  • Рекурсія в базі даних - WITH RECURSIVE для ієрархій, що зберігаються в таблиці, замість рекурсивних запитів з PHP (і N+1).

Захист від нескінченної рекурсії: умова зупинки на першому рядку і, для даних ззовні (зациклені посилання в графі), - облік уже відвіданих вузлів чи обмеження глибини.

Докладніше в документації: Функції користувача

4

Перевір себе

20 випадкових питань за спробу, після завершення - розбір кожної помилки

Схожі питання