Рекурсия
Цель сегодняшнего занятия познакомится с рекурсией, реккурентностями и алгоритмами их реализации.
К концу занятия Вы опираясь на полученные знания сможете самостоятельно изобразить алгоритм выполнения рекурсии.
Рекурсия - это одна из фундаментальных концепций в математике и программировании, Рекурсия - это одна из форм мышления, это мощное средство, позволяющее строить элегантные и выразительные алгоритмы.
Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.
Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.
Но рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом в программе (функции) должна присутствовать еще один важный элемент - так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс.
Рекуррентности.
Реккурентность - это рекурсивное определение функции. Они широко распространены в математике. Возможно наиболее знакомая Вам из такого рода функций - это факториал. Факториал - это произведение натуральных чисел от единицы до какого - либо данного натурального числа. Он определяется формулой:
N!=N((N-1)!, для N>=1 и 0! = 1.
Это напрямую соответствует нижеследующей рекурсивной программе:
function factorial( N : integer ) : integer;
begin
if N=0 then
factorial := 1
else
factorial := N *
factorial(N-1);
end;
Эта программа демонстрирует основные свойства рекурсивных программ: программа вызывает сама себя (с меньшим значением аргумента), и у нее есть терминальное условие при котором она прямо вычисляет результат.
Необходимо также помнить о том, что это - программа, а не формула: например ни формула, ни программа не работают с отрицательными N, но губительные последствия попытки произвести вычисления для отрицательного числа более заметны для программы, чем для формулы. Вызов factorial(-1) приведет к бесконечному рекурсивному циклу. Поэтому перед вызовом данной программы нужно делать проверку условия неотрицательности.
Второе, хорошо известное рекуррентное соотношение - соотношение определяющее числа Фибоначчи. Числа Фибоначчи - это элементы числовой последовательности 1,1, 2, 3, 5, 8 ..., в которых каждый последующий элемент равен сумме предыдущих.
FN = FN-1 + FN-2, где N >= 2 и F0 = F1 = 1.
И снова, рекуррентность соответствует простой рекурсивной программе:
function fibonacci( N : integer ) : integer;
begin
if N<=1 then
fibonacci := 1
else
fibonacci :=
fibonacci( N-1 ) +
fibonacci( N-2 );
end;
Как мы увидим, многие интересные алгоритмы можно легко реализовать с помощью рекурсивных программ, и многие разработчики алгоритмов предпочитают выражать алгоритмы рекурсивно. Но часто случается также и так, что столь же интересный алгоритм скрывается в деталях нерекурсивной реализации. Давайте рассмотрим такой алгоритм.
const
max = 25;
var
i : integer;
F : array [0..max] of integer;
procedure fibonacci;
begin
F[0] := 1;
F[1] := 1;
for i := 2 to max do
F[i] := F[i-1]+F[i-2];
end;
Эта программа вычисляет первые max чисел Фибоначчи, используя массив размера max. Этот метод называет итерационным.
Какой же метод лучше? Точных правил для выбора между рекурсивной и нерекурсивной версиями алгоритма решения задачи не существует. Краткость и выразительность большинства рекурсивных процедур упрощает их чтение и сопровождение. С другой стороны, выполнение рекурсивных процедур требует больших затрат и памяти, и времени процессора нежели их итерационные аналоги.
Деление пополам.
Большая часть алгоритмов использует два рекурсивных вызова, каждый из которых работает примерно с половиной входных данных. В дизайне алгоритмов такое явление называют "деление пополам"; его часто используют для достижения существенной экономии.
В качестве примера, давайте рассмотрим задачу нанесения делений на линейку: на ней должна быть метка в точке 1/2", метка немного покороче через каждые 1/4", еще более короткая через 1/8" и так.
 |
Линейка
Мы также предполагаем, что в наше распоряжение предоставлена процедура mark( x, h) для нанесения метки высоты h единиц на линейку в позицию x. Центральная метка должна иметь высоту n единиц, метки в центрах левой и правой половинок - n-1 единиц, и так далее. Следующая рекурсивная программа - прямой путь достижения нашей цели:
procedure rule( l, r, h : integer );
var m : integer;
begin
if h>0 then
begin
m := (l+r) div 2;
mark( m, h );
rule( l, m, h-1);
rule( m, r, h-1);
end;
end;
Идея этого метода заключается в следующем: для того, чтобы промаркировать линейку, мы сперва наносим длинную метку по ее середине. Это делит ее на две равные половины. Теперь мы наносим (более короткие) метки в середине каждой из этих половинок используя ту же самую процедуру.
Необходимо обращать особое внимание на терминальное условие рекурсивной программы - в противном случае она никогда не остановится! В вышеприведенной программе мы терминируем, когда мы должны нанести метку высоты 0. Рассмотрим пример, в результате вызова rule(0, 8, 3). Мы ставим метку по середине и вызываем rule для левой половины, затем делаем тоже самое для левой половины, и так далее пока высота метки не станет равна 0. В конечном итоге мы возвращаемся из rule и размечаем правую половину подобным образом.
|
rule(0,8,3) mark(4,3) rule(0,4,2) mark(2,2) rule(0,2,1) mark(1,1) rule(0,1,0) rule(1,2,0) rule(2,4,1) mark(3,1) rule(2,3,0) rule(3,4,0) rule(4,8,2) mark(6,2) rule(4,6,1) mark(5,1) rule(4,5,0) rule(5,6,0) rule(6,8,1) mark(7,1) rule(6,7,0) |
 |
Дерево рекурсивных вызовов для рисования линейки.
Другой нерекурсивный алгоритм заключается в том, чтобы рисовать сперва самые короткие метки, затем чуть менее короткие и так далее, как показано в следующей, довольно компактной, нерекурсивной программе:
procedure draw(l, r, h : integer);
var
i, j : integer;
begin
j:=1;
for i:=1 to h do
begin
for x:=0 to (l+r) div j do
mark(l+j+x*(j+j),i);
j:=j+j;
end;
end;
 |
Нерекурсивное рисование линейки
Сейчас создадим двухмерный узор демонстрирующий то, как простая рекурсия может дать решение тому, что кажется сложным.
 |
Фрактальная звезда (слева) и ее очертания(справа)
uses
graph,crt;
var
r,gd,gm: Integer;
procedure star(x,y,r:integer);
begin
if r>2 then begin
star(x+r,y+r,r div 2);
star(x+r,y-r,r div 2);
star(x-r,y-r,r div 2);
star(x-r,y+r,r div 2);
bar(x-r,y-r,x+r,y+r);
end;
end;
begin
clrscr;
Gd := Detect;
write('Enter the lenght: ');
readln(r);
InitGraph(Gd, Gm, 'с:\bp\bgi');
if GraphResult <> grOk then
Halt(1);
setbkcolor(0);
SetFillStyle(1, 9);
star(getmaxx div 2,getmaxy div 2,r);
repeat
until keypressed;
end.
Рисующий примитив здесь - просто процедура которая рисует квадрат размера 2r с центром в (x, y).
Рекурсивно определенные геометрические узоры подобные этому называют фракталами. Если используется более сложный примитив для рисования и более сложные рекурсивные вызовы (особенно на вещественной и комплексной плоскостях), то можно разработать узоры поразительной красоты и сложности.
 |
Итак, на сегодняшнем занятии мы познакомились с рекуррентостями и рекурсией.
