Презентация на тему Рекурсия. Перебор. Методы сокращения перебора

из неё же самой, непосредственно (простая рекурсия) или через

другие функции (сложная или косвенная рекурсия), например, функция А вызывает функцию B, а функция B — функцию A.
Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

реально необходима.
Числа Фибоначчи и факториалы – плохой пример использования

рекурсии
Рекурсия – это всего лишь вызов подпрограммы в самой себе
Рекурсия используется для разбиения задачи на подзадачи и решения задачи с объемом меньше, чем исходная.

сортировка (Хоара)
Обход различного рода деревьев (в повседневной жизни –

дерево каталогов)
Практически незаменима в переборных задачах

подпрограмм и их параметров
Следите за стеком.
Изменение размера стека:
Pascal:

{$M <размер стека в байтах>, <максимальный размер стека>}
С++: #pragma comment(linker, "/STACK:<размер стека в байтах>")

U2, …, UN (N – неизвестно)
Требуется построить вектор A

= (a1, a2, …, aN)
A1є U1, A2є U2, …, ANє UN
В алгоритме перебора вектор строится покомпонентно слева направо

Then
Else Begin
;
For

є Si>Do
Backtrack (<вектор + а>,i+1) ;
End;
End;

Франсуа Люка «Профессор Клаус»

Современное название головоломки

образом(пока непонятно каким) перенести n-1 дисков на промежуточный штырь
Перенесем

n-й диск на последний штырь
Таким же образом как и во втором шаге перенести n-1 дисков на последний штырь

если (количество > 0) то begin
номер_промежуточный = 6

- номер_1 - номер_2;
Перенести_диск(номер_1, номер_промежуточный, количество – 1);
Вывести_действие(номер_1, номер_2);
Перенести_диск(номер_промежуточный, номер_1, количество – 1);
end;
end;

с одними и теми же параметрами, т.е. выполняется «лишняя»

работа
Такая особенность рекурсии уменьшает эффективность

заключается в том, чтобы запомнить параметры уже вызывавшихся подпрограмм
В

случае если такие параметры повторяться, то не вызывать подпрограмму

целые параметры с небольшим диапазоном значений
Тогда для их хранения

достаточно n-мерного (n – число параметров функции) булевского массива
Если параметры имеют сложный вид, то необходимы сложные структуры данных, что вряд ли оправданно