Сравнение рекурсии и итерации

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

Основные понятия

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

Итерационный алгоритм повторяет действия явно: с помощью цикла for, while или другого управляющего средства. На каждой итерации изменяются переменные состояния, пока не выполнится условие остановки. Подробнее изменение счётчика и границы цикла важно проверять так же, как в теме изменение переменной цикла.

Как устроено выполнение

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

В цикле новый экземпляр функции не создаётся. Переменные состояния находятся в одной области выполнения, а переход к следующей итерации происходит после окончания тела цикла. Поэтому цикл обычно использует меньше памяти и имеет меньшие накладные расходы.

Здесь \(h\) — максимальная глубина рекурсии. Формула справедлива для линейной рекурсии, где каждый вызов создаёт не более одного следующего вызова и не требуется хранить дополнительный массив. Если функция создаёт несколько ветвей или сохраняет результаты, оценка памяти меняется.

Обе версии имеют одинаковый порядок времени, если на каждом шаге выполняют одну и ту же работу. Например, последовательное вычисление факториала занимает \(O(n)\) и при рекурсии, и при цикле; различается главным образом память.

Одна тапсырма в двух вариантах

Рассмотрим вычисление \(n! = 1\cdot2\cdot3\cdot\ldots\cdot n\). Рекурсивное определение естественно записывается так: \(0!=1\), а \(n!=n\cdot(n-1)!\). Циклическая версия последовательно накапливает произведение от \(1\) до \(n\).

1def factorial_recursive(n):
2    if n == 0:
3        return 1
4    return n * factorial_recursive(n - 1)
5
6
7def factorial_iterative(n):
8    result = 1
9    for value in range(2, n + 1):
10        result *= value
11    return result

В обеих программах выполняется төрт умножения для \(n=5\), то есть число действий линейно зависит от \(n\). Рекурсивная версия использует стек глубины 6: вызовы для \(5,4,3,2,1,0\). Циклу достаточно нескольких переменных.

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

Сначала определите, что изменяется от вызова к вызову. Если рекурсивный вызов просто уменьшает параметр на единицу, часто подходит цикл while немесе for. Если функция возвращает накопленный результат, заведите переменную-накопитель. Если рекурсия идёт по двум направлениям или возвращается к предыдущим состояниям, простой цикл может оказаться недостаточным.

1. Запишите базовый случай и условие продолжения.
2. Найдите параметр, который приближается к базовому случаю.
3. Создайте переменную состояния, соответствующую параметру функции.
4. Создайте накопитель результата, если значения перемножаются, складываются или объединяются.
5. Проверьте начальное значение и границы цикла на малых случаях: \(0\), \(1\), \(2\).

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

Однако рекурсия не всегда означает полный перебор. Например, алгоритм может рекурсивно обходить дерево, а число вызовов будет равно числу его вершин. И наоборот, цикл может содержать несколько вложенных циклов и реализовывать полный перебор. Оценивать нужно фактическое число состояний и переходов.

Когда какой способ выбирать

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

Выбирайте рекурсию, если задача естественно определяется через меньшую копию самой себя: дерево разбора, вложенные объекты, разбиение на подзадачи, поиск шешімдер тапсырма Водолей по графу состояний или другой обход графа. Но для графов рекурсивный обход требует пометки посещённых вершин; иначе возможен бесконечный переход по циклу.

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

Быстрая проверка