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

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

Рекурсия — это техника программирования, когда функция вызывает сама себя. Это мощный инструмент для решения задач, которые можно разбить на подзадачи того же типа. Рассмотрим детально.

Основные компоненты рекурсии

1. Базовый случай (Base Case) — условие выхода из рекурсии, предотвращающее бесконечный цикл.

2. Рекурсивный шаг (Recursive Case) — вызов функции с упрощёнными параметрами.

Простые примеры

Факториал:

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

echo factorial(5); // 120

Расчёт: factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → ... → 5 * 4 * 3 * 2 * 1 = 120

Сумма элементов массива:

function sumArray($arr, $index = 0) {
    // Базовый случай
    if ($index >= count($arr)) {
        return 0;
    }
    // Рекурсивный шаг
    return $arr[$index] + sumArray($arr, $index + 1);
}

echo sumArray([1, 2, 3, 4, 5]); // 15

Древовидные структуры

Рекурсия идеальна для работы с деревьями и графами:

class TreeNode {
    public $value;
    public $children = [];
}

function traverseTree(TreeNode $node) {
    echo $node->value . "\n";
    
    foreach ($node->children as $child) {
        traverseTree($child); // рекурсивный вызов
    }
}

Проблемы и оптимизация

1. Переполнение стека (Stack Overflow)

Каждый вызов функции использует память стека. Глубокая рекурсия может привести к ошибке:

// Опасно для больших $n!
function deepRecursion($n) {
    if ($n <= 0) return 0;
    return deepRecursion($n - 1);
}

Решение — увеличить limit: ini_set('memory_limit', '256M')

2. Хвостовая рекурсия (Tail Recursion)

Если рекурсивный вызов — последняя операция, компилятор может оптимизировать:

function factorialTail($n, $accumulator = 1) {
    if ($n <= 1) {
        return $accumulator;
    }
    return factorialTail($n - 1, $n * $accumulator); // хвостовой вызов
}

3. Мемоизация (Caching)

Для дорогостоящих рекурсивных вычислений кэшируйте результаты:

function fibonacci($n, &$cache = []) {
    if (isset($cache[$n])) {
        return $cache[$n];
    }
    
    if ($n <= 1) {
        return $n;
    }
    
    $cache[$n] = fibonacci($n - 1, $cache) + fibonacci($n - 2, $cache);
    return $cache[$n];
}

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

✓ Хорошо для:

• Древовидных структур (DOM, файловые системы)
• Разделяй и властвуй алгоритмов (быстрая сортировка, слияние)
• Обхода графов
• Комбинаторных задач

✗ Плохо для:

• Простых итеративных задач (используй циклы)
• Глубокой рекурсии (риск переполнения стека)
• Когда требуется высокая производительность

Рекурсия — элегантный способ решения многих задач, но требует аккуратности при реализации.