Сравнение рекурсивных и итеративных алгоритмов

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

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

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

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

Математическая модель итерации сводится к повторению некоторого преобразования (отображения) Т: Х→Х на множестве переменных программы Х (прямом произведении множеств значений отдельных переменных). Программной реализацией итерации является обычно некоторый цикл, тело которого осуществляет преобразование Т.

В качестве примера можно рассмотреть схему вычисления факториала натурального числа в соответствии с его математическим определением: n!=1∙2∙3∙…∙n. При написании программы в соответствии с ним нужно работать с двумя величинами целого типа Z_M: числом i, которое будет играть роль счетчика и изменяться от 1 до n включительно, и величиной f, в которой будет накапливаться произведение чисел от 1 до i.

Пространством X в данном случае будет Z²_M, в качестве начальной точки в этом пространстве возьмем точку (1, 1) (что соответствует i = k = 1), а преобразование Т: Х→Х будет иметь вид T(i,k)=(i+1,k*1). В случае, например, трехкратного применения преобразования T получим T(T(T(1,1)))=T(T(2,1))=T(3,2)=6, что обеспечит вычисление факториала числа 3.

Рекурсия и итерация взаимозаменяемы. Более точно, справедливо следующее утверждение.

Теорема. Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

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