Структуры и алгоритмы

Цель сегодняшнего занятия познакомится с рекурсией, реккурентностями и алгоритмами их реализации.

К концу занятия Вы опираясь на полученные знания сможете самостоятельно изобразить алгоритм выполнения рекурсии.

Рекурсия - это одна из фундаментальных концепций в математике и программировании, Рекурсия - это одна из форм мышления, это мощное средство, позволяющее строить элегантные и выразительные алгоритмы.

Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.

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

Реккурентность - это рекурсивное определение функции. Они широко распространены в математике. Возможно наиболее знакомая Вам из такого рода функций - это факториал. Факториал - это произведение натуральных чисел от единицы до какого - либо данного натурального числа. Он определяется формулой:

Это напрямую соответствует нижеследующей рекурсивной программе:

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 ..., в которых каждый последующий элемент равен сумме предыдущих.

И снова, рекуррентность соответствует простой рекурсивной программе:

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).

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

Итак, на сегодняшнем занятии мы познакомились с рекуррентостями и рекурсией.