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

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

Как это работает

Рекурсивная функция состоит из двух обязательных частей:

• Базовый случай — условие, при котором функция прекращает вызывать себя и возвращает конкретное значение. Без базового случая рекурсия станет бесконечной и приведёт к переполнению стека вызовов.
• Рекурсивный случай — условие, при котором функция вызывает саму себя с изменёнными параметрами, приближаясь к базовому случаю.

Каждый вызов функции помещается в стек вызовов. Когда функция вызывает саму себя, новый вызов добавляется в стек, и так до достижения базового случая. Затем вызовы начинают возвращать значения в обратном порядке, освобождая стек.

Пример: вычисление факториала

Классический пример — вычисление факториала числа N (обозначается как N!). Факториал натурального числа N — это произведение всех натуральных чисел от 1 до N. Его можно выразить рекурсивно: N! = N * (N-1)!.

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

echo factorial(5); // Вывод: 120

Здесь при n = 5 функция вызывает себя с n = 4, затем с n = 3 и так далее, пока n не станет равным 1. После этого начинается обратный ход: каждый вызов возвращает результат умножения, и в итоге получается 120.

Другие применения

Рекурсия широко используется для обхода иерархических структур данных, например:

• Обход дерева каталогов файловой системы.
• Обход дерева элементов пользовательского интерфейса (DOM).
• Поиск в глубину (DFS) в графах.
• Алгоритмы сортировки, такие как быстрая сортировка и сортировка слиянием.

В таких задачах рекурсия позволяет элегантно описать алгоритм, который естественным образом повторяется на каждом уровне вложенности.

Подводные камни

Рекурсия — мощный инструмент, но требует осторожности:

• Бесконечная рекурсия — если базовый случай не определён или недостижим, функция будет вызывать себя бесконечно, что приведёт к переполнению стека и ошибке.
• Переполнение стека — глубокая рекурсия может исчерпать память стека вызовов. В PHP глубина рекурсии ограничена (обычно около 100–200 тысяч вызовов, но зависит от конфигурации). Для очень глубоких рекурсий лучше использовать итеративные алгоритмы.
• Производительность — рекурсивные вызовы требуют дополнительных ресурсов на создание нового кадра стека. В некоторых случаях итеративное решение может быть быстрее и экономичнее по памяти.

Когда использовать

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

Коротко

• Рекурсия — вызов функции самой себя с обязательным базовым случаем.
• Базовый случай останавливает рекурсию, рекурсивный случай приближает к нему.
• Пример: факториал, обход деревьев, алгоритмы сортировки.
• Остерегайтесь бесконечной рекурсии и переполнения стека; для глубоких рекурсий предпочтительны итерации.