15.5.2. Преимущества и недостатки рекурсивных алгоритмов

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

Несомненным достоинством алгоритмов из примеров 8, 10 является их простота и обоснованность. При программировании мы по–существу одновременно обосновывали правильность алгоритма. В примерах 7, 9 рассматривались комбинаторные задачи, решение которых не сводится к простому применению цикла, а требует перебора вариантов, естественным образом управляемого рекурсивно. Итеративные версии решений этих задач сложнее по управлению. Можно сказать, что основная вычислительная сложность комбинаторной задачи заключена не в реализации алгоритма ее решения, а в самом методе решения.

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

15.5.3. Метод “разделяй и властвуй” (рекурсивная процедура)

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

Отличительный признак метода – разбиение задачи на равные по сложности подзадачи. Эффективность получаемого алгоритма зависит, во-первых, от количества действий, затраченных на сведение задачи к подзадачам, во–вторых – баланса сложностей подзадач.

Классический пример применения метода – бинарный поиск в упорядоченном массиве. Массив разбивается на две равные части. Используя затем два сравнения, алгоритм либо находит элемент, либо определяет ту половину, в которой его следует искать – т.е. сводит задачу размера n к задаче размера n/2. Рассмотрим известное решение задачи поиска минимального и максимального элемента в массиве, основанное на этом методе.

Пусть A[1..n] – числовой массив. Требуется найти Max(A) и Min(A). Предположим, что n=2^k. Такое предположение дает возможность делить массив и все получаемые в процессе вычи­слений его части пополам.

Опишем основную процедуру MaxMin. Пусть S – некоторое множество и |S|=m. Разобьем S на равные по числу элементов части: S=S₁S₂, S₁S₂ = , |S₁| = m/2, |S₂| = m/2. Найдем Max1, Min1 как результат MaxMin(S₁) и Max2, Min2 как результат MaxMin(S₂).

Затем Max := Max(Max1, Max2); Min := Min(Min1, Min2);

procedure MaxMin(L, R : Integer; Var Max, Min : Real);

Var Max1, Min1, Max2, Min2 : Real;

Begin { L, R – границы индексов массива A }

If R – L = 1

then If A[L] > A[R] { выбор Маx, Min за одно сравнение }

then begin

Max := A[l]; Min := A[R] end

else begin

Max := A[R]; Min := A[L] end

else begin

C := (R + L – 1) div 2;

MaxMin(L, C, Max1, Min1);

MaxMin(C+1, R, Max2, Min2);

If Max1 > Max2 then Max := Max1 else Max := Max2;

If Min1 < Min2 then Min := Min1 else Min := Min2

end

End;

Пусть С(n) – оценка сложности процедуры MaxMin в терминах сравнений. Тогда, очевидно

С(2) = 1,

C(n) = 2 C(n/2) + 2 при n > 2

Отcюда С(n) = 2 (n/4 + n/8 + ... + 1) + n/2 = 2(n/2 – 1) + n/2; C(n) = 3/2 n – 2.

Для сравнения заметим, что алгоритм поиска Max и Min методом последовательного просмотра массива требует 2n–2 сравнений. Таким образом, применение метода “разделяй и властвуй” уменьшило временную сложность задачи в фиксированное число раз. Разумеется, истинная причина улучшения – не в применении рекурсии, а в том, что максимумы и минимумы двух рядом стоящих элементов массива ищутся за одно сравнение! Метод позволил просто и естественно описать вычисления.

Длина цепочки рекурсивных вызовов в алгоритме равна log₂ n –1, и в каждой копии используются 4 локальных переменных. Поэтому алгоритм использует вспомагательную память объема O(log₂ n), распределяемую динамически. Это – плата за экономию времени.