Использование рекурсии для перебора вариантов (Паскаль)

Поиск информации, удовлетворяющий определённым условиям (критериям), осуществляется перебором всех элементов структуры данных и их проверкой на удовлетворение условиям поиска.
При переборе возможных вариантов рекурсия возникает естественным образом.
Перебор без повторений – нахождение способов исключения из перебора бесперспективных с точки зрения условия задачи вариантов.
Перебор с возвратом – метод проб (пример с лабиринтом).
Ханойская башня – пример программы с использованием рекурсивного определения процедуры.
Двоичный поиск (binary search) – алгоритм поиска индекса элемента в упорядоченном массиве, с применением метода деления массива пополам:
- выбор «барьерного» значения ключа;
- разделение массива на две части, левую и правую;
- взаимное упорядочение двух частей (подмассивов) так, чтобы все элементы левой части не превосходили элементов правой части;
- применение рекурсии, при которой подмассив упорядочивается точно таким же способом, как и весь массив.

Было полезно?

Предыдущий конспект

Следующий конспект