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