Lect12 – Рекурсия

1. Рекурсия

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
1

2. Идея

• Функция, вызывающая саму себя
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
2

3. Факториал

• N! = 1 * 2 * 3 * 4 * … * N-1 * N
• 1! = 1
• 2! = 1*2
• 3! = 1*2*3
• 4! = 1*2*3*4
• 5! = 1*2*3*4*5
• N! = N * (N-1)!
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
3

4. Факториал

int factorial(int x){
if(x<=1){
return 1;
}
return x*factorial(x-1);
}
int main(){
cout << factorial(5) << endl;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
4

5. Факториал

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
5

6. Примеры в математике

• Факториал
– N! = 1 * 2 * 3 * 4 * … * N-1 * N
– N! = N * (N-1)!
• Фибоначчи
– FIB(1) = 1
– FIB(2) = 1
– FIB(N) = FIB(N-1) + FIB(N-2)
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
6

7. Примеры в математике

int gcd(int a, int b){
if(b==0){
return a;
} else {
return gcd(b, a%b);
}
}
int main(){
cout << gcd(121, 88) << endl;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
7

8. Стек вызов: перепишем функцию

int factorial (int x){
if(x<=1){
return 1;
}
int y = factorial (x-1);
return x*y;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
8

9. Стек вызовов

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
9

10. Стек вызовов

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
10

11. Стек вызовов

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
11

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

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
12

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

bool isEven(int n) {
if (n == 0)
return true;
else
return isOdd(n - 1);
}
bool isOdd(int n) {
if (n == 0)
return false;
else
return isEven(n - 1);
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
13

14. Используем рекурсию

• Решаем, надо ли нам использовать
рекурсию
• Выбираем ключевой параметр
• Описываем условия выхода
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
14

15. Нужна ли нам рекурсия

• Стек вызовов занимает память
• Есть доступ только к данным из текущего
вызова
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
15

16. Нужна ли нам рекурсия?

int factorial(int x){
if(x<=1){
return 1;
}
return x*factorial(x-1);
}
int factorial(int x){
int fact = 1;
for(int i=2;i<x;i++)
fact*=i;
return fact;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
16

17. Нужна ли нам рекурсия?

int fib(int x){
if(x<=2){
return 1;
}
return fib(x+1)+fib(x+2);
}
int fib(int x){
int f1 = 1, f2=1, f3 = 1;
for(int i=3;i<x;i++){
f3 = f1+f2;
f2 = f3;
f1 = f2;
}
return f3;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
17

18. Фиббоначи

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
18

19. Фиббоначи

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
19

20. Ключевой параметр

• Рекурсия – решение проблемы через
постоянное её уменьшение
• Если есть уменьшение, есть размер
• Если есть размер – его можно посчитать
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
20

21. … и точка выхода

• Рекурсия должна остановиться
• В рекурсивной функции ВСЕГДА есть ветка,
не содержащая нового вызова
• Выход всегда определяется ключевым
параметром
• В косвенной рекурсии такой ветки
достаточно в одной из функций
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
21

22. Еще примеры

• Разделяй и властвуй в целом
• Сложные реккурентные соотношения
• Парсеры
• Фракталы
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
22

23. Разделяй-и-властвуй

• Быстрая сортировка
• Сортировка слиянием
• Подели задачу на две меньшие по объему
• Реши каждую из подзадач и объедини
результат
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
23

24. Быстрая сортировка

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
24

25. Двоичный поиск

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
25

26. Реккурентные выражения

• Длина стороны многоугольника
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
26

27. Парсеры

• Распознавание текстов, выражений,
программ
• Построено на использовании формальных
грамматик
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
27

28.

Пусть будет дана грамматика G:
G6 = ({S}, {a, +, *}, P, S),
Где P определяется как:
1. S a
2. S S + S
3. S S * S
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
28

29.

S
1
S
S
2
3
S
S
4
5
S
S
6
a
+
a
*
7
a
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
+
a
29

30. Фракталы

• Геометрические структуры, описывающиеся
через себя самих
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
30

31. Кривая Коха

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
31

32. Кривая Минковского

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
32

33. Кривая Леви

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
33

34. Пирамида

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
34

35. Пирамида

void pyramid(int size){
if(size==0){
return;
}
pyramid(size-1);
for(int i=0;i<size;i++)
cout << "*";
cout << endl;
pyramid(size-1);
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
35