Рекурсия

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

Если уже работал с 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

<?php
declare(strict_types=1);

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

// Поднять программно (если 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() для похожих задач:

<?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";
}

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

<?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 ещё не содержит само замыкание.

Рекурсия 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;
}

<ComparisonTable data={{ headers: ["", "Рекурсия", "Итерация"], rows: [ ["Читаемость", "Для деревьев, графов - понятнее", "Для линейных задач - проще"], ["Память", "O(n) стек вызовов", "O(1)"], ["Скорость", "Overhead на вызовы функции", "Обычно быстрее"], ["Лимиты PHP", "max_nesting_level / memory_limit", "Нет ограничений на глубину"], ["Когда", "Деревья, вложенные структуры, графы", "Массивы, числа, линейные задачи"] ] }} />

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

<?php
declare(strict_types=1);

// ОШИБКА 1: нет базового случая
function infinite(int $n): int
{
    return $n + infinite($n - 1); // Fatal error: Maximum function nesting level reached
}

// ОШИБКА 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)