Виды рекурсивных структур данных

Рис. 56. Схема рекурсивного вычислительного процесса

Рис. 55. Схема итеративного процесса

В основе итеративного вычислительного процесса лежит итеративный цикл While, Repeat-Until, For. Наиболее общим является цикл While:

While < условие цикла > do < тело цикла >;

Итеративная схема вычисления факториала:

N! = 1 * 2 * 3 * … * N.

Процедура, реализующая итеративную схему вычисления факториала:

Procedure Iter_Fact (n: word; var f: word);
Var i: word;
begin
i:=1; f:=1;	{ инициализация }
while i < = n do begin	{ решение о завершении }
f:= f * i;	{ вычисления }
inc(i);	{ модификация }
end;
end;

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

1. Любой итеративный цикл может быть заменен рекурсией.

2. Рекурсия не всегда может быть заменена итерацией.

Рекурсивная схема организации вычислительного процесса

Общая схема рекурсивного вычислительного процесса представлена на рис. 56.

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

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

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

Общая схема рекурсивного цикла:

Procedure Рекурсивный_Цикл (…);

begin

if < условие цикла > then

begin

< тело рекурсивного цикла; >

Рекурсивный_Цикл (…);

end;

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

Общая схема бесконечного рекурсивного цикла:

Procedure Бесконечный_Рекурсивный_Цикл (…);

begin

if < условие цикла > then

begin

Бесконечный_Рекурсивный_Цикл (…);

< тело рекурсивного цикла; >

end;

Рекурсивная схема вычисления факториала:

Базисная часть:

0! = 1; 1! = 1;

Рекурсивная часть:

N! = N * (N-1)! = N * (N-1) * (N-2)! = N * (N-1) * … * (N – (N-1))! =

Процедура, реализующая рекурсивную схему вычисления факториала:

Procedure Recurs_Fact (n: word; var f: word);
begin
if n <= 1 then	{ принятие решения о завершении вычислений:}
f:=1;	{ да - окончательные вычисления для базисной части }
else begin
Recurs_Fact (n-1, f);	{ нет - промежуточные вычисления и обращение процедуры к самой себе }
{ 1 } f:=f * n;	{ окончательные вычисления для рекурсивной части }
end;
{ 2 } end;

{ 1 } – адрес возврата после завершения активации,

{ 2 } – завершение активации.

С каждым обращением к рекурсивной процедуре ассоциируется номер уровня рекурсии (номер фрейма активации). Считается, что при первоначальном вызове рекурсивной процедуры из основной программы номер уровня рекурсии равен единице. Каждый следующий вход в процедуру имеет номер уровня на единицу больше, чем номер уровня процедуры, из которой производится это обращение. Другой характеристикой рекурсивной процедуры является глубина рекурсии, определяемая максимальным уровнем рекурсии в процессе вычисления при заданных аргументах. В общем случае эта величина неочевидна, исключение составляют простые рекурсивные функции: например, при вычислении значения N! глубина рекурсии равна N.

Так как при выходе из текущей активации самым первым должен быть восстановлен фрейм, который был позже всех сохранен, для хранения фреймов используется автоматическая память, т.е. область системного стека (см. 3.2.2). Таблица 3 и рис. 57 поясняют механизм рекурсивных вычислений.

Таблица 3. Трасса вычисления 3!

Рис. 57. Фреймы активации при вычислении 3!

6.2. Задача о “ханойских башнях”

Согласно легенде, у жрецов храма Брахмы в горах Тибета есть медная платформа с тремя алмазными стержнями A, B и C. На одном стержне А нанизано 64 золотых диска, каждый из которых немного меньше того, что под ним. Конец света наступит, когда жрецы переместят диски со стержня А на стержень С. Задача имеет следующие условия:

¨ за один раз можно перемещать только один диск,

¨ больший диск нельзя класть на меньший,

¨ снятый диск нельзя отложить, его необходимо сразу же надеть на другой стержень.

Несомненно жрецы все еще работают, т.к. задача включает в себя 2⁶⁴ – 1 ходов. Если тратить по одной секунде на ход, то потребуется примерно 500 миллиардов лет.

Решение данной задачи носит рекурсивный характер. Задача разбивается на последовательность подзадач одного и того же типа, но меньшей размерности. Условием завершения является выполнение простой задачи перемещения одного диска.

Сформулируем алгоритм решения данной задачи для N дисков. Обозначим стержни: начальный (start), промежуточный (temp), конечный или целевой (destination). На начальный стержень нанизано N дисков в порядке возрастания размера, т.е. самый большой диск лежит внизу. Цель задачи – переместить все N дисков с начального стержня на конечный, следуя определенным выше условиям, и распечатать перечень ходов. Предполагается, что промежуточный стержень будет использоваться для временного хранения дисков.

Если N = 1, выполняется условие завершения (базисное условие рекурсивного алгоритма), которое может быть обработано путем перемещения единственного диска с начального стержня на конечный и распечатки соответствующего хода.

Для N > 1 выполняется трехшаговый процесс перемещения N дисков с начального стержня на конечный, причем стержень А является начальным (A – start), стержень В – промежуточным (B – temp), стержень С – конечным (C – dest).

На первом шаге алгоритма перемещаются N – 1 дисков с начального стержня на промежуточный с использованием конечного стержня для временного хранения. При этом стержень А выполняет роль начального (A – start), стержень В выполняет роль конечного (B – dest). Конечный стержень С используется как промежуточный (C – temp).

На втором шаге самый большой диск просто перемещается с начального стержня на конечный: start -> dest.

На третьем шаге N – 1 дисков перемещаются со среднего стержня на конечный с использованием начального стержня для временного хранения. При этом стержень B выполняет роль начального (B – start), стержень C выполняет роль конечного (C – dest). Начальный стержень А используется как промежуточный (A – temp).

Программная реализация алгоритма решения задачи о “ханойских башнях” приведена ниже.

{ перенести N дисков с начального стержня на конечный, используя промежуточный стержень для временного хранения дисков }
Procedure Hanoi(n: byte; start, tmp, dest: char);
begin
if (n=1) then	{ условие завершения: перемещение одного диска }
writeln(start, ‘-->’ dest)
else begin
{ перенести N–1 дисков с начального стержня на промежуточный, используя конечный стержень для временного хранения дисков }
Hanoi(n-1, start, dest, temp);
{ перенести нижний диск с начального стержня на конечный }
writeln(start, ‘-->’ dest);
{ перенести N–1 дисков с промежуточного стержня на конечный, используя начальный стержень для временного хранения дисков }
Hanoi(n-1, temp, start, dest)
end;
end;

Более короткий вариант решения задачи о “ханойских башнях”:

{ перенести N дисков с начального стержня на конечный, используя промежуточный стержень для временного хранения дисков }
Procedure Hanoi(n: byte; start, tmp, dest: char);
begin
if (n>0) then begin	{ условие продолжения }
{ перенести N–1 дисков с начального стержня на промежуточный, используя конечный стержень для временного хранения дисков }
Hanoi(n-1, start, dest, temp);
{ перенести нижний диск с начального стержня на конечный }
writeln(start, ‘-->’ dest);
{ перенести N–1 дисков с промежуточного стержня на конечный, используя начальный стержень для временного хранения дисков }
Hanoi(n-1, temp, start, dest)
end;

Иллюстрация решения задачи для N = 1 диска приведена на рис. 58, для N = 2 дисков приведена на рис. 59, для N = 3 дисков – на рис. 60. Алгоритм требует 2^N – 1 ходов.

И все же рекурсивные алгоритмы наиболее эффективны и удобны для обработки рекурсивных структур данных.