Рекурсивные подпрограммы

Пример рекурсивного алгоритма

Задача. Двумерный массив целых чисел представляет цвета клеток рисунка. Найдите самую большую связную область одного цвета. (Связи по диагонали не учитываются.)

Алгоритм решения

Будем считать, что цвета задаются целыми положительными числами. В процессе работы программы будем изменять значения пройденных клеток на 0. Кроме того, обрамим исходный массив каймой из нулей, чтобы предотвратить выход за его границы без дополнительных проверок на каждом шагу рекурсии. Теперь массив будет задан не как

array[1..N,1..M] of byte;

а как

array[0..N+1,0..M+1] of byte;

Теперь опишем рекурсивную процедуру, делающую по массиву один "шаг вперед":

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

После того как мы посетим все клетки, найденный максимум можно будет объявить итоговым.

Замечание. Рекурсивный алгоритм обхода можно представить в двух вариантах: "посмотрел-шагнул" и "шагнул-посмотрел". Другими словами, в первом случае мы сначала выбираем подходящее место для шага вперед и только потом делаем этот шаг (что очень хорошо сообразуется с правилами передвижения, скажем, по болоту). Во втором же случае мы сначала делаем шаг вперед и только потом проверяем, что же именно оказалось у нас под ногами. Все-таки "ходим" мы не по болоту и в любой момент можем "спастись" из неправильно выбранной клетки.

Стековая организация рекурсии

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

Если некоторая подпрограмма в процессе выполнения вызывает другую подпрограмму, то для вызванной процедуры или функции создается новый отдельный контекст ( контекст вызвавшей подпрограммы при этом сохраняется) и т.д. Активным в каждый момент времени является последний контекст. После ликвидации текущего активного контекста активным становится последний "отложенный" контекст - тот, из которого только что закрытый и был вызван.

Таким образом, на внутреннем уровне организован стек контекстов подпрограмм.

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

procedure razlozh(k,t:integer; s:string);
var i: integer;
			sss: string;
begin
	for i:= t to trunc(sqrt(k)) do
		if k mod i = 0
			then begin
							str(i,sss);
							razlozh(k div i, i,s+sss+'*');
				end;
str(k,sss);
s:=s+sss;
writeln(s);
end;
begin
	readln(n);
	razlozh(n,2,'');
end.

Для n = 24 стек контекстов этой программы пройдет последовательно такие стадии (значения параметров указаны на моменты вызова процедуры, состояния стека приведены только на моменты времени, предшествующие закрытию очередного контекста ):

Непосредственно перед закрытием самого верхнего контекста происходит печать на консоль. Таким образом, на экране появляются результаты:

2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
24

Ограничение глубины рекурсии

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

Следовательно, каждая рекурсивная подпрограмма должна содержать в себе признак окончания - своеобразный "забор", определяющий максимальную глубину вложенности для этой рекурсии. Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным (в частности, описанная выше процедура razlozh рано или поздно обязательно закончится, поскольку на каждом шаге происходит уменьшение разлагаемого натурального числа).

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

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

Если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной. Линейную рекурсию довольно легко заменить итеративным алгоритмом. Например, можно реализовать функцию факториала, определенную в начале пункта " Рекурсия ", двояко.

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;

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

Пример сравнения рекурсивного и нерекурсивного алгоритма

Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?

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

Рекурсивный алгоритм

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

Реализация рекурсивного алгоритма

program pohod_rec;
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() - как не представляющую особенного интереса.

Реализация нерекурсивного алгоритма

program pohod;
const nnn = 100;            {максимально возможное количество различных весов}
var f: text;
    d,razn,k,i,j,n: integer;
    sum: longint;
    ves,kol: array[1..nnn] of word;
    take, dif: array[0..nnn] of word;

procedure vyvod(a: integer);
begin
    writeln(a);
    halt;           {принудительное завершение работы программы}
end;

begin
{---- Ввод данных и их сортировка ---}
    ...
{---- Основная часть программы -----}
    d:= sum mod 2;          {показатель четности общего веса}
    sum:=(sum div 2)+ d;    {"большая половина" общего веса}

    dif[0]:= sum;
    razn:= sum;
    for i:= 1 to k do
        begin
            take[i]:= min(dif[i-1] div ves[i],kol[i]);
            dif[i]:= dif[i-1]- take[i]*ves[i];
            if dif[i]< razn then razn:= dif[i];
            if razn <= d then vyvod(d);
    {проверка того, что уже на первом шаге найдено решение}
        end;

{---- Заполнение массива --------}
    i:= k;
    while i>0 do
        begin
            if take[i]= 0
                then i:= i-1                {переход к следующей компоненте}
                else begin		
                    dec(take[i]);            уменьшение текущей компоненты на 1}
                    inc(dif[i],ves[i]);     {увеличение остатка на соотв. величину}
                    for j:= i+1 to k do     {перезаполнение хвоста}
                    begin
                    take[j]:= min(dif[j-1] div ves[j],kol[j]);
                    dif[j]:= dif[j-1]- take[j]*ves[j];
                    if dif[j]< razn then razn:= dif[j];
                    if razn <= d then vyvod(d); {проверка результата}
                end;
                i:= k;
            end;
        end;
    vyvod(2*razn-d);
end.

Иллюстрация

Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.

Пусть имеется семь предметов ( n = 7 ) с весами 9, 5, 25, 11, 9, 5, и 11 единиц (килограмм, фунтов, бушелей...). Тогда всего есть четыре разных вида предметов ( k = 4 ).

Общая сумма весов равна 75 ; следовательно, "большая половина" sum = 38. Теперь нужно найти такой набор предметов, чей суммарный вес будет наиболее близким к этой "золотой середине". Кроме того, не стоит забывать и о сделанном ранее замечании: как только найдется набор, вес которого отличается от "золотого" лишь на единицу, поиск можно закончить.

Начнем теперь заполнять массивы take и dif (массив dif хранит остатки, в пределах которых можно проводить дальнейшие вычисления).

На начальном ("нулевом") шаге мы заполним массив take так, чтобы в создаваемый набор попали по возможности самые тяжелые предметы (см. раздел реализации "Основная часть программы"). Таким образом, получим следующие состояния массивов:

После этого шага переменная razn, которая хранит отклонение текущего набора весов от оптимального, будет содержать значение 2. Попытаемся уменьшить это значение (переход к разделу реализации "Заполнение массива").

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

Таким образом, наши массивы последовательно примут следующие значения (некоторые непринципиальные шаги опущены):

1

2

3

4

5

6

7

10

12

17

22

24

Итак, мы убедились в том, что найденное в самом начале значение переменной razn и было минимальным (найденные группы весов соответственно 25 + 11 = 36 и 11 + 9 + 9 + 5 + 5 = 39 ). Необходимо отметить, что из приведенных выше таблиц видно (см. шаг 5), что существует еще один способ разделить приведенный набор весов таким же оптимальным образом: ( 11 + 11 + 9 + 5 = 36 и 25 + 9 + 5 = 39 ). Найденная разница 39 - 36 = 3 и будет окончательным результатом, который программа сообщит пользователю.

Эффективность

В отличие от рекурсивного алгоритма, верхним пределом для которого можно смело считать наборы длиной в 50 предметов, итеративный алгоритм способен обработать до 5 000 различных весов (общее количество предметов может быть гораздо больше).

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

Быстрая сортировка

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

Алгоритм Быстр

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

Теперь применим эти же действия к левой и к правой части массива - рекурсивно.

Реализация алгоритма Быстр

type index = 1..N;
var a: array[index] of integer;

procedure quicksort(l,r:index);
	var i,j: index; 
		  x,z: integer;
	begin
			i:= l;
			j:= r;
			x:= a[(l+r)div 2];
			repeat
					while a[i]< x do inc(i);
					while a[j]> x do dec(j);
					if i <= j
						then begin
									z:= a[i];
									a[i]:= a[j];
									a[j]:= z;
									inc(i);
									dec(j);
								end;
				until i>j;
			if l<j then quicksort(l,j);
			if i<r then quicksort(i,r);
	end;
begin   {тело программы}
	...
	quicksort(1,n);
	...
end.

Эффективность алгоритма Быстр

Алгоритм Быстрой сортировки имеет в среднемСуществует, однако, "плохой" случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N-1 и 1 ). Поэтому при описании эффективности мы использовали слова "в среднем". сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100 ).

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