ТЕМА: «РЕКУРСИИ»

В общем случае для правильной организации рекурсивных алгоритмов необходимо выполнение двух условий:

Ø должно быть найдено представление общей задачи в терминах «более простой» задачи того же класса, которое определит последовательность рекурсивных вызовов;

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

В общем виде рекурсивное описание подпрограммы должно иметь одну из следующих структур или некоторую эквивалентную форму:

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

Пример 1. Вычисление факториала.

{Нисходящая рекурсия}

program Factorial;

var n:byte;

function Fact(n:byte):longint;

begin {Fact}

if n=0 then fact:=1 {терминальная ветвь}

else fact:=n*fact(n-1) {рекурсивная ветвь}

end; {Fact}

begin {Factorial}

write(‘Введите n’);

readln(n);

writeln(‘Факториал’,n:2,’=’,fact(n))

end. {Factorial}

Вызов, например, fact(5) означает, что функция fact вызывает себя раз за разом: fact(4), fact(3), … до тех пор, пока не будет достигнута терминальная ситуация. При каждом вызове текущие вычисления «откладываются», локальные переменные и адрес возврата сохраняются в стеке. Терминальная ситуация fact:=1 достигается при n=0. По достижении терминальной ситуации рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных на данный момент копий функции: начинает строиться ответ: n*fact(n-1), сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 – передаются вызывающими функциями. Латинское recurrere означает «возвращение назад».

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

Пример 2. Вычисление факториала.

{Восходящая рекурсия}

program Factorial;

var n:byte;

function Fact(n:byte,w:longint):longint;

begin {Fact}

if n=0 then fact:=w {терминальная ветвь}

else fact:=fact(n-1,n*w) {рекурсивная ветвь}

end;{Fact}

begin {Factorial}

write(‘Введите n’);

readln(n);

writeln(‘Факториал’,n:2,’=’,fact(n,1))

end. {Factorial}

Здесь w – рабочий параметр, применяемый для формирования результата. При первом вызове функции этот параметр надо инициализировать (придать ему начальное значение – 1), далее при каждом рекурсивном вызове, например, при вычислении 5!, он принимает последовательно значения: 5*1, 4*5*1, 3*4*5*1, 2*3*4*5*1, 1*2*3*4*5*1.

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

В следующем примере показана рекурсивная процедура с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

Пример 3. Счет от n до 1 на рекурсивном спуске и от 1 до n на рекурсивном возврате. При этом видно, как заполняется и освобождается стек.

{Выполнения рекурсивных действий}

{до и после рекурсивного вызова }

program Stack;

var n:integer;

procedure recursion(i:integer);

begin {Recursion}

writeln(i:30); {Вывод на рекурсивном спуске}

if i>1 then recursion(i-1);

writeln(i:3); {Вывод на рекурсивном возврате}

end; {Recursion}

begin {Strak}

write(‘Введите n:’);

readln(n);

writeln;

writeln(‘Рекурсия:’);

recursion(n)

end. {Stack}

В процедуре Recursion операция writeln(i:30) выполняется перед рекурсивным вызовом, после чего writeln(i:3) освобождает стек. Поскольку рекурсия выполняется от n до 1, вывод по writeln(i:30) выполняется в обратной последовательности: n, n-1,…, 1, а вывод по writeln(i:3) – в прямой: 1, 2, …, n (согласно принципу LIFO – «последним пришел, первым обслужен»).

Возможная глубина рекурсивных вычислений определяется размером используемого стека. Насколько велик стек, можно установить с помощью бесконечной рекурсии. Причем использование директивы {$S+} при переполнении стека приведет к прерыванию программы с выдачей сообщения «Error 202: stack overflow error» («Ошибка 202: переполнение стека»).

Пример 4. Определение размера стека.

{Программа проверки размера стека}

program Stack test;

{$S+} {Включить контроль переполнения стека}

procedure proc(i:integer);

begin {proc}

if i mod 1024=0 then writeln(i:6);

proc(i+1)

end; {proc}

begin {Stack_test}

proc(1)

end. {Stack_test}

Стек связан с другой структурой памяти – с динамической областью. С помощью директивы {$M} можно управлять размером стека.