Въведение в алгоритмите. Рекурсия и итерация. Лекция

Въведение в алгоритмите.
Рекурсия и итерация.
Лекция 2

Дисциплина: Синтез и анализ на алгоритми

Доц. Е. Сотирова

1. Рекурсия
Рекурсивен е обект, който се
дефинира чрез самия себе си.
Средство за рекурсивно изразяване в
програмите са функциите:
 Пряко рекурсивни функции F

F

 Непряко рекурсивни функции

F1F2...FnF1.

F1

F2

Fn

…

2. Рекурсивен алгоритъм
 Реализация на рекурсивен алгоритъм:

 Разбиване на задачата на подзадачи, за които

рекурсивно може да се приложи същият
алгоритъм;
 Дъно на рекурсията.
 Рекурсията поддържа стек (със

стойностите на локалните и формални
параметри от всяко рекурсивно
обръщение);
 Резултатите от nтото обръщение се,
връщат на (n-1)то и т.н. до първото
обръщение.

n
2
1

3. Факториел
n!  n * ( n  1) * ( n  2) * ... * 2 *1
(дъно на

1,
n 0 рекурсията)
n! f (n)  
n * f (n  1) n  0
Разгъване и свиване на рекурсията

n=4

n= n-1=3

n= n-1=2

n= n-1=1