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


Результат функции рекурсивного поиска


До сих пор мы рассматривали варианты рекурсивных функций с логическим результатом. В этом случае производился поиск первого подходящего варианта. Причем данные самого варианта (например, путь к выходу из лабиринта) могли храниться в глобальных переменных. Если же допустимых вариантов несколько, то алгоритм несколько усложнится . Воспользуемся предыдущим примером для иллюстрации вносимых изменений .

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


xxx step(char *lw)
{ ...
for (...)
{ ...
if (step(pw))
{}
}
return ...}

Далее, изменения будут касаться самого принципа формирования результата. Каждый шаг рекурсивного алгоритма получает несколько различных результатов от рекурсивных вызовов, обрабатывает их и формирует собственный результат аналогичного типа. Обработка может заключаться в простейшем случае в выборе варианта, соответствующего заданному критерию и передаче (ретрансляции) его " наверх" (например, выбор минимального или максимального из полученных). В более сложных случаях к результатам " примешиваются" данные текущего шага. Так или иначе, возврат результатов от разветвляющейся рекурсии должен идти в обратном порядке


char *s(...)
{ char *p;
p=s(...); // вызов char *s(){...}


if (...) p=s(...); // вызов char *s(){...}


if (...) p=s(...); // вызов char *s(){...}


}

Следующий важный принцип заключается в том, что результат рекурсивной функции должен представлять структуру данных, полностью содержащую все данные о найденном варианте, использование глобальных переменных здесь невозможно. Обычно такие данные имеют переменную размерность и для их представления используются динамические структуры данных (динамические массивы, списки и т.д.). В предыдущем примере результатом рекурсивной функции поиска может быть строка (в динамической памяти), содержащая цепочку, выведенную из оставшихся слов, начиная с заданного формальным параметром. При этом естественно отсекаются недопустимые варианты (из оставшихся слов цепочка не выводится) путем возврата NULL.




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



Книжный магазин