Практическо упражнение №6

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

Цел на упражнението

:  

Запознаване с понятието рекурсия. Разглеждане на основните схеми за 

работа с линеен едносвързан списък (създаване, обхождане и търсене на елемент) – рекурсивна 
техника.

1. Рекурсия. Рекурсивна дефиниция на свързан списък.

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

или структура от данни чрез самата себе си. 

Силата на рекурсията се състои във възможността за дефиниране на безкрайно множество от 

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

Ако една процедура 

P

 съдържа обръщение към себе си, се казва, че тя е 

пряко рекурсивна

; 

ако  

P

  съдържа  обръщение   към друга  процедура  

Q

,  която  от  своя  страна   съдържа  (пряко  или 

непряко) обръщение към 

P

, се казва, че 

P

 е 

непряко рекурсивна.

Обикновено за процедурата се дефинират параметри и локални за нея обекти (константи, 

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

P

  да   се   подчинява   на   условие  

B

,   което   в   даден   момент   да   престава   да   бъде 

удовлетворено. Следователно, схемата на рекурсивна процедура може да се изрази по-точно така:

procedure 

P

;

begin

if B then 

begin
  

...

P

;

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

end

end;

Рекурсивните алгоритми са особено подходящи, когато проблемът, който ще се решава или 

структурата от данни, която ще се обработва, са рекурсивни.

Пример за рекурсивно дефиниран проблем е функцията 

факториел

:

N!=N*(N-1)*(N-2)*…*2*1, 

като се приема, че 

0!=1

, т.е

1,

N=0

N! = 

N*(N-1)!, 

N>0

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

•

чрез рекурсивна функция;

Function 

Fact

(N:integer):integer;

Begin

If  N=0  then Fact:=1

   else Fact:=N*

Fact

(N-1);

End;

Гл.ас. Е. Големанова

583310_pomagalo_com.doc

Упражнение № 6

=1=