Рекурсия и поисковые задачи
С помощью рекурсии легко решаются задачи, связанные с поиском, основанном на полном или частичном переборе возможных вариантов. Принцип рекурсивности заключается здесь в том, что процесс поиска разбивается на шаги, на каждом из которых выбирается и проверяется очередной элемент из множества, а алгоритм поиска повторяется, но уже для " оставшихся" данных. При этом вовсе не важно, каким образом цепочка шагов достигнет цели и сколько вариантов будет перебираться. Единственное, на что следует обратить внимание - корректность очередного шага.
Само множество, в котором производится поиск, обычно реализуется в виде глобальных данных, в которых каждый шаг выбирает необходимые элементы, а по завершении поиска возвращает их обратно.
При реализации поисковых задач следует обратить внимание на результат рекурсивной функции. Он непосредственно связан с организацией процесса поиска и перебора вариантов :
-если рекурсивная функция имеет результат void, то она не может повлиять на характер протекания процесса поиска и реализуемый алгоритм будет выполнять полный перебор всех возможных вариантов (если только для связи рекурсивных вызовов не будут использоваться глобальные данные) ;
-если рекурсивная функция выполняет поиск первого попавшегося варианта, то результатом ее является как правило логическое значение (в Си - 0 /1). При этом " ИСТИНА" соответствует успешному завершению поиска, а " ЛОЖЬ" - неудачному. Общим для всех алгоритмов поиска является : если рекурсивный вызов возвращает " ИСТИНУ" , то она должна быть немедленно " передана наверх" , то есть текущий вызов также должен быть завершен со значением " ИСТИНА" . Если рекурсивный вызов возвращает " ЛОЖЬ" , по поиск должен быть продолжен. При завершении полного перебора всех вариантов рекурсивная функция также должна возвратить " ЛОЖЬ" ;
-если в процессе поиска производится более сложный анализ и сравнение вариантов, то рекурсивная функция и, соответственно, шаг процесса должны производить выбор между подходящими вариантами, в целью выбора наиболее оптимального.
Обычно для этого используется минимум или максимум какой-либо характеристики выбираемого варианта. Тогда рекурсивная функция возвращает значение, которое является оценкой для оставшихся не просмотренных элементов, а текущий рекурсивный вызов выбирает из них минимум или максимум с учетом данных текущего шага.
Все сказанное о результате рекурсивной функции касается только самого процесса выбора вариантов. Открытым остается вопрос о том, как возвратить саму цепочку выбранных из множества элементов, дающих оптимальный результат. Здесь также возможны варианты :
-рекурсивная функция сама выводит выбранный элемент в случае успешного поиска (это приемлемо, если осуществляется поиск первого попавшегося варианта, но не очень хорошо с точки зрения технологии программирования) ;
-выбранный элемент записывается в область глобальных данных, в которых моделируется стек для возврата результата ;
-в качестве результата функции используются более сложные, динамические структуры данных, например, список результатов.
Все перечисленные принципы так и останутся пустым звуком, если их не проиллюстрировать на примерах рекурсивных программ.
