Информатика и технология программирования


Рекурсия и поисковые задачи


С помощью рекурсии легко решаются задачи, связанные с поиском, основанном на полном или частичном переборе возможных вариантов. Принцип рекурсивности заключается здесь в том, что процесс поиска разбивается на шаги, на каждом из которых выбирается и проверяется очередной элемент из множества, а алгоритм поиска повторяется, но уже для " оставшихся" данных. При этом вовсе не важно, каким образом цепочка шагов достигнет цели и сколько вариантов будет перебираться. Единственное, на что следует обратить внимание - корректность очередного шага.

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

При реализации поисковых задач следует обратить внимание на результат рекурсивной функции. Он непосредственно связан с организацией процесса поиска и перебора вариантов :



-если рекурсивная функция имеет результат void, то она не может повлиять на характер протекания процесса поиска и реализуемый алгоритм будет выполнять полный перебор всех возможных вариантов (если только для связи рекурсивных вызовов не будут использоваться глобальные данные) ;



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



-если в процессе поиска производится более сложный анализ и сравнение вариантов, то рекурсивная функция и, соответственно, шаг процесса должны производить выбор между подходящими вариантами, в целью выбора наиболее оптимального.


Начало  Назад  Вперед