Рекурсия

При дефиниране на тялото на дадена функция винаги в нея може да бъде извикана друга такава. Повечето от съвременните езици позволяват в тялото на функцията тя да вика сама себе си.Този механизъм се нарича рекурсивен, а функцията- рекурсивна. Характерни за тях са следните свойства:

1. Наличие на няколко тривиални случая, при които на функцията се задава директна стойност. Примерно сумата от първите п

числа е 0 за n=0.

2. Параметър, който задава стъпката (размерността) на функцията в повечето случаи е 1.

3. Изразяване на който и да който и да било случай с помощта на няколко по- прости такива. Целта е разлагането на даден обект на няколко по- прости обекти, но с по-малка размерност докато не

се стигне до тривиален случай.

Типичен пример за рекурсивна функция е функцията факториел:

function fact(n:integer):integer;

begin

if n=0 then fact:=1

else fact:=n*fact(n-1)

end;

Как точно действа тази функция? Приемаме за пример че n=3.

1. n=3 следователно fact:=3*fact(2)

2. fact(2) = 2* fact(1)

3. fact(1) = 1* fact(0)

4. fact(0)=1 по дефиниция

По същия алгоритъм само че в обратен ред замествайки стойностите на функцията ще получим:

1. fact(1)=1*1

2. fact(2)=2*1

3. fact(3) = 3*2

В крайна сметка функцията ще върне стойност 6.

Всяка задача, която може да бъде изпълнена с рекурсивна функция може да се зададе и по стандартен начин с определен брой и вид цикли. В такива моменти си задаваме въпроса кой е по удачния вариант. За да можем да си отговорим на този въпрос трябва да съблюдаваме три основни фактора. Това са сложността и дължината на кода, с който се дефинира функцията и броя обръщения и съответно пресмятания и не на последно място количеството на паметта, която ни е нужна за да работи нашата функция. От горния пример много добре се вижда, че факториелната функция е "жадна" за памет. Това е така защото всяко нейно междинно състояние се пази в стека.

Типичен пример за функция, която изисква повече ресурси като е зададена по рекурсивен начин отколкото по итеративен. При всяко обръщение в рекурсивния вариант функцията изчислява две стойности на параметъра "(n-1) и (n-2)". Неефективността идва от многократното пресмятане за една и съща на аргумента- например за п=5 fib(2) се пресмята три пъти.