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

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

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

Пример 9.2

Реализовать рекурсивное и итеративное вычисление факториала натурального числа п > 0.

Решение

Программный код решения задачи с пояснениями приведен в листинге 9.3. Он достаточно прост и в особых пояснениях не нуждается.

Листинг 9.3

Program factorial;

Var

n, i, fact_i:longint;

{Функция для рекурсивного вычисления факториала} function fact (n:longint):longint; begin

if n=0 then fact:=l else fact:=n*fact (n-1); end;

begin {Основная программа}.

write ('Введите целое неотрицательное n: '); readln (n);

{Рекурсивное вычисление факториала}.

writeln ('Рекурсивное вычисление: fact (n));

{Итеративное вычисление} if n=0 then fact_i:=l else begin

fact_i:=1;

for i:=l to n do fact_i:=fact_i*i; end;

writeln ('Итеративное вычисление: ¹, fact_i); end.

Результат выполнения программного кода при п = 15 приведен в листинге 9.4. ?

Листинг 9.4

Введите целое неотрицательное п: 15 Рекурсивное вычисление: 2 004 310 016 Итеративное вычисление: 2 004 310 016.

Пример 9.3

Реализовать рекурсивное и итеративное вычисление чисел по формулам Фибоначчи F_m (т > 0).

Решение

Программный код решения задачи с пояснениями приведен в листинге 9.5. Он достаточно прост и в особых пояснениях не нуждается.

Листинг 9.5

Program fibonacci;

Var

m, i, fibon_i:longint;

f_ml, f_m2:longint; {Предыдущие два числа Фибоначчи).

function fibon (m:longint):longint; begin

if (m=0) or (m=l) then fibon:=m; if m>=2 then fibon:=fibon(m-1)+fibon(m-2); end;

begin {Основная программа).

write ('Введите целое неотрицательное m для вычисления m-го числа Фибоначчи: '); readln (ш);

{Рекурсивное вычисление факториала).

writeln ('Рекурсивное вычисление: ', fibon (ш));

{Итеративное вычисление) if (m=0) or (m=l) then fibon_i:=m else begin

fibon_i:=0; f_m2:=0; f_ml:=1;

for i:=2 to m do begin

f ibon_i:=f_m2 + f_ml; f_m2:= f_ml; f_ml:= f ibon_i; end;

end;

writeln ('Итеративное вычисление: ', fibon_i); end.

Результат выполнения программного кода при п = 15 приведен в листинге 9.6. ?

Листинг 9.6.

Введите целое неотрицательное m для вычисления m-го числа Фибоначчи: 44 Рекурсивное вычисление: 701 408 733 Итеративное вычисление: 701 408 733^[1][2][3][4]

• 1) каким образом выбирать опорный элемент?
• 2) каков алгоритм перестановки элементов до и после опорного?

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

• • oporn: =а [random (R-L+l)-1 ] — случайный элемент из подмассива a [L]. .а [R];
• • oporn: =а [ (R+L) div 2 ] ] — элемент, разделяющий подмассив a[L]. .a[R] примерно пополам. В приведенном ниже программном коде будет использован именно этот вариант.

Размещение элементов перед и после опорного выполняется следующим образом:

• 1) пусть i и j — номера первого и последнего элементов разделяемого множества соответственно. Изначально принимается i = LJ = R
• 2) будем последовательно увеличивать i на 1 до тех пор, пока не встретим первый с начала подмассива элемент, больший или равный опорному, — а [ i ] >=oporn;
• 3) будем последовательно уменьшать j на 1, пока не встретим первый с конца подмассива элемент, меньший или равный опорному, —

а [ j ] <=oporn;

4) если i < j, то выполняем перестановку, а [ i ] и, а [ j ] и переходим снова к шагу 2; иначе процесс размещения элементов окончен.

В результате выполнения шагов 1—4 элементы, меньшие опорного или равные ему, окажутся слева, а большие или равные — справа от него.

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

Рассмотренный алгоритм быстрой сортировки является одним из часто применяемых на практике ввиду относительной простоты реализации и действительно быстрой работы. Алгоритм имеет среднюю степень роста 0(nogn)_y что является очень хорошим показателем его эффективности. Также он имеет относительно небольшую глубину и максимальный уровень рекурсии. При этом размер требуемого стека невелик.

Вместе с тем алгоритм имеет ряд недостатков:

• • считается, что алгоритм становится эффективен при п > 40. Поэтому, когда размер подмассива меньше 40, используются и программно реализуются другие алгоритмы сортировки (вставкой, пузырьковая и др.) Это требует дополнительных трудозатрат;
• • если в качестве опорного элемента выбрать максимальный (минимальный) элемент подмассива или близкий к нему по значению элемент, то алгоритм становится крайне неэффективным. В этом случае степень роста может стать близкой 0(п²). Это приведет к существенному возрастанию глубины рекурсии.

Программный код решения задачи сортировки массива со случайными элементами приведен в листинге 9.7. Для понимания работы алгоритма в код были включены операторы вывода дополнительной информации:

• • границы обрабатываемого подмассива при каждом вызове процедуры quicksort (отмечено комментарием *);
• • индекс и значение опорного элемента (отмечено комментарием * *);
• • выполняемые перестановки (отмечено комментарием ***);
• • промежуточное состояние сортируемого массива (отмечено комментарием ****).

Данные операторы не являются обязательными.

Листинг 9.7

Program qsort; const

n=16;(Количество элементов сортируемого массива} type

myarray = array[l.n] of integer;

Var

i, j: integer; a: myarray;

{Процедура быстрой сортировки; b — псевдоним подмассива массива а}.

procedure quicksort(var b: myarray; L, R: integer); var

oporn, i_oporn, k: integer; {Опорный элемент и его индекс} begin

{*} writeln ('Обрабатываемый подмассив: а [', L, ' ].. а [', R / ' ] ') ;

i_oporn:=((L+R) div 2); {В качестве опорного выбирается средний элемент} oporn:=b[i_oporn];

{**} writeln (' Опорный элемент а[', i_oporn,']=', oporn); i:=L; j:=R; {Установка начального и конечного значения индексов сортируемого подмассива}.

while i<=j do begin

while b[i]do inc (i); {Ищется первый с начала подмассива элемент, больший опорного}.

while b[j]>oporn do dec (j); {Ищется первый с конца подмассива элемент, меньший опорного}.

if i<=j then {Если больший опорного элемент находится не правее меньшего} begin

{***} writelnf' Перестановка a[', i,'] и, а [ ', j, ' ] ') ;

swap (b[i], b[j]); {Поменять местами} inc (i); dec (j); {Изменить счетчики, так как b[i] и b[j] стоят на своих местах}.

end;

end;

{****} writeln ('Промежуточный массив:');

{Проверка} for к: = 1 to n do

write (а[к],' '); writeln; writeln;

{Если левая граница не совпадает с последним элементом с конца, меньшим опорного, то для оставшейся части массива вызвать рекурсивно эту же процедуру. Для правой границы аналогично} if Lthen quicksort (b, L, j); if R>i then quicksort (b, i, R);

end;

begin {Тело основной программы}.

{Формирование массива и вывод на экран} writeln ('Исходный массив:'); for i := 1 to n do begin

a[i]: =random (100); write (a[i], ' ') ;

end;

writeln; writeln;

{Вызов процедуры быстрой сортировки} quicksort (а, 1, n);

{Вывод отсортированного массива} writeln ('Отсортированный массив:'); for i := 1 to n do write (a[i],' '); end.

Результат выполнения программы при п = 16 приведен в Приложении 4. ?

• [1] Пример 9.4 Реализовать алгоритм быстрой сортировки для одномерного числового массива. Решение Алгоритм быстрой сортировки (Quick Sort) является одним из самых используемых на практике для упорядочивания больших объемовданных. Он был предложен в 1960 г. Ч. Хоаром. Пусть дан массив, а из п элементов, а [ 1 ], а [ 2 ] ,…, а [ п ], и его требуется упорядочить по возрастанию. Алгоритм быстрой сортировкив укрупненном виде может быть записан следующим образом:
• [2] среди элементов сортируемого массива, а [ 1 ], pet, а [ 2 ] ,…, а [ п ]выбрать некоторый элемент oporn=a [k], 1 < k < п} называемый опорным. Алгоритм выбора опорного элемента дан ниже;
• [3] сравнить оставшиеся элементы с опорным и разместить меньшие (или равные) слева от него, а большие (или равные) — справа;
• [4] повторить рекурсивно шаги 1—2 для каждой части до и послеопорного элемента. Можно показать, что при выполнении шагов 1—3 массив будет упорядочен, но возрастанию. Если упорядочивать таким образом, чтобы нашаге 2 элементы, большие опорного, были слева от него, а меньшие —справа, то массив будет упорядочен по убыванию. Пусть L и R (L < К) — индексы начала и конца сортируемого массива. Поскольку алгоритм быстрой сортировки является рекурсивным, то будет описан общий алгоритм для некоторого подмассиваa [L].. a [R] массива а, где 1 < L < п и 1 < R < п. При практическом использовании алгоритма быстрой сортировкизначимыми оказываются два вопроса, которые существенно влияют навременную сложность: