Рекурсия. 1 курс

1. Рекурсия

Григорьева
Анастасия Викторовна
1

2. Рекурсия

Чтобы понять рекурсию, надо понять
рекурсию
Не забывайте условие выхода из
рекурсии
Не забывайте возвращать значения из
рекурсивной функции
Вербовка по телефону
Какая самая типичная задача для
рекурсии?
2

3. Типичные задачи на рекурсию

n!
Числа Фибоначчи
Ханойские башни
Сортировки (QuickSort, MergeSort)
Самые эффективные из универсальных рекурсивные
Множество других
3

4. Первый пример. Факториал

n!
n!=1*2*3*...*n. С другой стороны,
4

5. Нод

5

6. Факториал №351

10! = 3628800
Unsignet long fact(int n) {…}
6

7. Бинарный поиск

7

8. Бинарный поиск

8

9. Бинарный поиск

9

10. Ханойские башни № 3050

Void Hanoi(n, i, j, k)
10

11. Решение

11

12. Алгоритм быстрого возедения в степень

12

13. Встроенные алгоритмы сортировки в С++

https://youtu.be/tUfR7sorYcs
Sort(a.begin(), a.end())
Sort(a.rbegin(), a.rend())
Sort(a.begin(), a.end(), cmp)
Функция-компаратор всегда реализует сравнение типа "меньше". То
есть если cmp(x, y) возвращает истину, то по нашему правилу
сравнения x должен стоять в отсортированном массиве раньше y

14. Сортировка по сумме цифр. №112319

15. Поиск в глубину

Напишите программу, которая распечатывает кол-во одинаковых элементов в
матрице, которые находятся рядом (по диагонали не в счет):
15

16. Решение Сортировки по сумме цифр

17. Сортировка слиянием

https://youtu.be/pqomcdA-whg
https://habr.com/ru/post/281675/

18. Пример

СПбГУ, 2021

19. MergeSort

СПбГУ, 2021

20. Сортировка слиянием

СПбГУ, 2021

21. Сортировка слиянием

22. Оценка времени при записи рекуррентным соотношением