Правила форума
Лекция №9.3: Рекурсивные подпрограммыСодержание
Замена рекурсивных алгоритмов итеративными
Поскольку новый контекст создаётся каждый раз, когда очередной экземпляр рекурсивной подпрограммы (сам ещё оставаясь незавершённым) заново вызывает себя же, то память компьютера расходуется очень быстро. Поэтому рекурсию при всей её наглядности нельзя отнести к экономичным способам программирования. Существует даже специальная наука — динамическое программирование, изучающая способы замены рекурсивных алгоритмов адекватными итеративными алгоритмами. Мы не станем сейчас углубляться в изложение принципов динамического программирования, а ограничимся лишь примерами превращения рекурсивных программ в нерекурсивные.
Если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной. Линейную рекурсию довольно легко заменить итеративным алгоритмом. Например, можно реализовать функцию факториала, определённую в начале пункта «Рекурсия», двояко.
| Рекурсивная реализация | Итеративная реализация |
|---|---|
function Fact(k : Byte) : LongInt; var x : LongInt; begin if k = 0 then fact := 1 else begin x := fact(k - 1) * k; fact := x; end; end; | fact := 1; for i := 2 to k do fact := fact * i; |
Если же каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или «ветвящейся». Для того, чтобы превратить такую рекурсию в итеративный алгоритм, придётся приложить много усилий и, возможно, даже внести некоторые изменения в обрабатываемую структуру данных. Примером «ветвящейся» рекурсии может служить рассмотренная выше процедура разложения числа на сомножители.
Пример сравнения рекурсивного и нерекурсивного алгоритма
Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?
(Имеется набор натуральных чисел, быть может, с повторениями. Необходимо разделить его на два поднабора так, чтобы разность сумм весов была минимальной.)
Рекурсивный алгоритм
Нужно перебрать все возможные подмножества заданного набора весов. Для решения этой задачи существует несколько классических алгоритмов, мы воспользуемся простейшим, который носит название «полный перебор». В полном соответствии со своим названием, этот алгоритм перебирает все возможные варианты наборов.
Реализация рекурсивного алгоритма
var f : Text;
a : array[1 .. 100] of Integer;
n : Integer;
min, obsh_ves : LongInt;
procedure step(t : Byte; ves : LongInt);
var j : LongInt;
begin
j := Abs(obsh_ves - 2 * ves);
if j < min then
min := j;
for j := t + 1 to n do
step(j, ves + a[t]);
end;
begin
Assign(f, 'in');
Reset(f);
n := 0; {кол–во всех предметов}
obsh_ves := 0;
while not Eof(f) do
begin
Inc(n);
Read(f, a[n]);
Inc(obsh_ves, a[n]);
end;
Close(f);
min := MaxLongInt;
step(1, 0);
WriteLn('difference ', min)
end.
Полный перебор с отсечением
Приведённая выше программа делает много лишней работы. Скажем, незачем продолжать генерирование очередного набора после того, как текущая разность уже превысила ранее найденный минимум. Кроме того, если в некоторый момент времени минимум вдруг окажется равным 1 или 0 (в зависимости от чётности входных данных), то дальнейшие усилия также становятся ненужными, поскольку всё равно ничего меньшего быть не может.
С учётом этих замечаний можно усовершенствовать текст программы. Мы оставляем эту несложную работу желающим.
Нерекурсивный алгоритм
Здесь нам потребуется несколько дополнительных рассуждений и линейных массивов.
Основная часть приводимой ниже программы является итеративной реализацией алгоритма полного перебора всех возможных вариантов, удовлетворяющих входным ограничениям. Её основное отличие от рекурсии — использование малого объёма памяти для хранения текущих данных. Вся информация хранится в массивах ves, take и dif. Для вычислений на каждом шаге используется только эта информация. Такой подход позволяет избежать непрерывных перевычислений, которые и являются причиной «тяжеловесности» рекурсивного алгоритма.
Итак, первая часть программы должна заниматься подсчётом и упорядочением вводимых предметов по убыванию их весов. Для экономии места мы не станем приводить подробную реализацию этого блока: здесь годится любой метод сортировки (см. лекцию 4). Важно лишь, что в результате этой сортировки все входные данные будут записаны в два линейных массива длины k (количество разных весов).
Считаем теперь, что массив ves хранит различные веса предметов, упорядоченные по убыванию, а массив kol — количество предметов каждого веса.
Кроме того, в процессе ввода данных производится суммирование весов всех предметов, этот общий вес записывается в переменную sum. Правда, затем эта же переменная будет хранить не весь общий вес, а только его половину (с учётом чётности исходной суммы) — для удобства дальнейших сравнений.
Мы не приводим в тексте программы и реализацию функции min() — как не представляющую особенного интереса.
::
::
::
