Слайд 2
![Рекурсия. Определение В программировании рекурсия — вызов функции (процедуры) из](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-1.jpg)
Рекурсия. Определение
В программировании рекурсия — вызов функции (процедуры) из неё же
самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция А вызывает функцию B, а функция B — функцию A.
Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Слайд 3
![Рекурсия. Основные положения Рекурсию надо использовать там, где она реально](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-2.jpg)
Рекурсия. Основные положения
Рекурсию надо использовать там, где она реально необходима.
Числа Фибоначчи
и факториалы – плохой пример использования рекурсии
Рекурсия – это всего лишь вызов подпрограммы в самой себе
Рекурсия используется для разбиения задачи на подзадачи и решения задачи с объемом меньше, чем исходная.
Слайд 4
![Примеры использования рекурсии Поиск в глубину в графе Сортировка слиянием](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-3.jpg)
Примеры использования рекурсии
Поиск в глубину в графе
Сортировка слиянием
«Быстрая» сортировка (Хоара)
Обход различного
рода деревьев (в повседневной жизни – дерево каталогов)
Практически незаменима в переборных задачах
Слайд 5
![Стек вызовов Рекурсия использует системный стек для запоминания вызываемых подпрограмм](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-4.jpg)
Стек вызовов
Рекурсия использует системный стек для запоминания вызываемых подпрограмм и их
параметров
Следите за стеком.
Изменение размера стека:
Pascal: {$M <размер стека в байтах>, <максимальный размер стека>}
С++: #pragma comment(linker, "/STACK:<размер стека в байтах>")
Слайд 6
![Рекурсия. Иллюстрация](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-5.jpg)
Слайд 7
![Перебор с помощью рекурсии Даны N упорядоченных множеств U1, U2,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-6.jpg)
Перебор с помощью рекурсии
Даны N упорядоченных множеств U1, U2, …, UN
(N – неизвестно)
Требуется построить вектор A = (a1, a2, …, aN)
A1є U1, A2є U2, …, ANє UN
В алгоритме перебора вектор строится покомпонентно слева направо
Слайд 8
![Перебор с помощью рекурсии. Общая схема](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-7.jpg)
Перебор с помощью рекурсии. Общая схема
Слайд 9
![Перебор с помощью рекурсии. Схема реализации Procedure Backtrack ( );](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-8.jpg)
Перебор с помощью рекурсии. Схема реализации
Procedure Backtrack (<вектор,i>);
Begin
If <вектор является решением>
Then <записать его>
Else Begin
<вычислить Si>;
For
Do
Backtrack (<вектор + а>,i+1) ;
End;
End;
Слайд 10
![Задача о Ханойских башнях. История Древняя индийская легенда 1883 г.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-9.jpg)
Задача о Ханойских башнях. История
Древняя индийская легенда
1883 г. Франсуа Люка «Профессор
Клаус»
Современное название головоломки
Слайд 11
![Ханойские башни. Решение Допустим на штыре n дисков Необходимо каким-то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-10.jpg)
Ханойские башни. Решение
Допустим на штыре n дисков
Необходимо каким-то образом(пока непонятно каким)
перенести n-1 дисков на промежуточный штырь
Перенесем n-й диск на последний штырь
Таким же образом как и во втором шаге перенести n-1 дисков на последний штырь
Слайд 12
![Ханойские башни. Графическая иллюстрация решения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-11.jpg)
Ханойские башни. Графическая иллюстрация решения
Слайд 13
![Ханойские башни. Алгоритм решения. Функция Перенести_диск(номер_1, номер_2, количество) begin если](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-12.jpg)
Ханойские башни. Алгоритм решения.
Функция Перенести_диск(номер_1, номер_2, количество)
begin
если (количество >
0) то begin
номер_промежуточный = 6 - номер_1 - номер_2;
Перенести_диск(номер_1, номер_промежуточный, количество – 1);
Вывести_действие(номер_1, номер_2);
Перенести_диск(номер_промежуточный, номер_1, количество – 1);
end;
end;
Слайд 14
![Меморизация. Предпосылки При реализации рекурсивных подпрограмм часто вызываются подпрограммы с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-13.jpg)
Меморизация. Предпосылки
При реализации рекурсивных подпрограмм часто вызываются подпрограммы с одними и
теми же параметрами, т.е. выполняется «лишняя» работа
Такая особенность рекурсии уменьшает эффективность
Слайд 15
![Меморизация. Что это? От английского слова memo – памятка. Идея](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-14.jpg)
Меморизация. Что это?
От английского слова memo – памятка.
Идея заключается в том,
чтобы запомнить параметры уже вызывавшихся подпрограмм
В случае если такие параметры повторяться, то не вызывать подпрограмму
Слайд 16
![Меморизация. Особенности Эффективна, когда рекурсивная процедура или функция имеет целые](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-15.jpg)
Меморизация. Особенности
Эффективна, когда рекурсивная процедура или функция имеет целые параметры с
небольшим диапазоном значений
Тогда для их хранения достаточно n-мерного (n – число параметров функции) булевского массива
Если параметры имеют сложный вид, то необходимы сложные структуры данных, что вряд ли оправданно
Слайд 17
![Спасибо за внимание!](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/414524/slide-16.jpg)