Содержание
- 2. Общее определение Реку́рсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно
- 3. Рекурсия типов данных: Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при
- 4. Рекурсия функций Рекурсия функции— это вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или
- 5. Общий вид рекурсии: Если (простейший случай) тогда Решить напрямую Иначе Делать рекурсивный вызов до появления простейшего
- 6. Задача о вычислении Факториала Вычисление факториала – пример задачи, в которой мы можем использовать рекурсию. Факториал
- 7. Однако мы можем выразить факториал рекурсивно, через другие факториалы: 5! = 5 * 4! 4! =
- 8. Пример реализации функции на с++ int factorial(int n) { if (n == 0) { // простейший
- 9. Ханойские башни: В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают
- 10. Помочь уничтожить мир! Данная задача имеет элегантное рекурсивное решение: Итак, нам необходимо перенести n дисков со
- 11. Функция на с++ void Step(int n, char a, char b, char c) // n - количество
- 12. Цена рекурсии Использование рекурсии может сократить размер исходного кода программы и сделать код более элегантным и
- 13. Пример: Вычисление чисел фибоначчи long fib( int n ) { if( n return n; else return
- 14. Повторное вычисление значений Рассмотрим визуализацию рекурсивного подсчета чисел фибоначчи: Можно заметить, что F(3) вычисляется три раза.
- 15. Улучшения Для избавления от вычисления одних и тех же значений можно где-то хранить уже посчитанные значения,
- 16. Требовательность к памяти Алгоритмы, использующие рекурсию весьма требовательны к памяти. Вернемся к примеру с рекурсивным вычислением
- 17. Рекурсия и стек Каждый шаг рекурсии представляет собой независимый алгоритм (отдельный «экземпляр» функции). В случае ветвящейся
- 18. Схема рекурсивного алгоритма с явным стеком stack S; // Явный стек data D0={…}; // Начальное состояние
- 19. Волновой алгоритм Рекурсивный алгоритм дает нам последовательность выполнения шагов, известную как «рекурсивный обход дерева», которая определяется
- 20. Задача поиска минимального пути Идея «волны» иногда позволяет резко сократить число просматриваемых вариантов в сравнении с
- 21. Пример реализации // Поиск кратчайших путей на графе – волновой алгоритм #define N 100 int A[N][N];
- 22. Продолжение for (i=0;i if (A[ni][i]!=0){ // Это неотмеченный сосед if (W[i]==-1 || W[i]>W[ni]+A[ni][i]) { //или сосед
- 23. Резюме Таким образом, Всегда полезно подумать о замене рекурсии на циклические алгоритмы. Однако в некоторых случаях
- 25. Скачать презентацию