Рекурсия. Рекурсивни техники за обработка на списъци.

Рекурсията е метод в математиката и програмирането за дефиниране на функция, процедура или структура от данни чрез самите себе си.

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

Ако една процедура P съдържа обръщение към себе си, се казва, че тя е пряко рекурсивна; ако P съдържа обръщение към друга процедура Q, която от своя страна съдържа (пряко или непряко) обръщение към P, се казва, че P е непряко рекурсивна.

Обикновено за процедурата се дефинират параметри и локални за нея обекти (константи, типове, променливи и други процедури и функции). Всеки път, когато такава процедура се активира рекурсивно, се създава ново копие на локалните променливи и параметри. Макар, че те имат същите имена, стойностите им са различни от тези на по-горното ниво на рекурсията. Всички недоразумения , които могат да възникнат вследствие на еднаквите имена, се избягват чрез правилата за област на действие на идентификаторите. Друг проблем при рекурсивните алгоритми е осигуряването на край на изълнението. Очевидно, основно изискване е рекурсивното извикване на процедурата P да се подчинява на условие B, което в даден момент да престава да бъде удовлетворено. Следователно, схемата на рекурсивна процедура може да се изрази по-точно така:

procedure P;

begin

if B then

begin

...

P; {рекурсивно извикване}

end

end;

Рекурсивните алгоритми са особено подходящи, когато проблемът, който ще се решава или структурата от данни, която ще се обработва, са рекурсивни. Списъците и дърветата са типични примери на рекурсивни структури данни. Например, списък от елементи от тип Т, дефиниран рекурсивно е следното:

• празен списък (nil);

• последователност от елемент от тип T (глава) и списък от елементи от тип T (опашка);

1. Създаване на едносвързан линеен списък от тип FIFO (опашка).

• чрез рекурсивна процедура;

var head:point;

Procedure Create(var p:point);

var x: integer;

begin

readln(x);

if x=0 then p:=nil