<<
>>

4.4. РЕКУРСИВНЫЕ АЛГОРИТМЫ

Изучая в предыдыщем разделе язык Паскаль, мы уже использовали понятие рекурсии. Однако, оно столь важно и принципиально, что с ним следует познакомиться детальнее. Рекурсией называют метод определения или вычисления функции, процедуры или решения задачи посредством тон же функции, процедуры и т.д.
Рекурсивные алгоритмы широко используют методы частных целей, подъема и отрабатывания назад. На эвристическом уровне рекурсия позволяет эффективно использовать метод проб и ошибок. Продолжим рассмотрение примера задачи тура шахматного коня из предыдущего раздела. Приведенный там алгоритм строил возможный путь коня по простой стратегии очередного хода на свободное место по принципу часовой стрелки. Однако, он не позволял гарантированно найти полный тур коня. Применим простую эвристическую модель решения задачи - в случае отсутствия возможности очередного хода осуществляется возврат коня на предыдущее поле и возобновление поиска дальнейшего маршрута по другому пути. Подобный процесс называют возвратом (или откатом). Его можно осуществлять по универсальной схеме: procedure RETR; begin инициализация начального хода repeat выбор очередного хода if подходит then его запись; if решение не полное then RETR; if неудача then стирание хода и возврат на предыдущий until удача or нет хода end.
Подобная рекурсивная процедура и уже известный алгоритм, рассмотренный выше, позволяют построить нужную программу. Ниже представлена программа тура коня для произвольного поля NxN, позоляющая отыскивать полный тур с любого начального положения. Для наглядной иллюстрации процесса поиска в глубину и в ширину с возвратами в программе в комментарные скобки обозначены команды вывода промежуточных результатов. Программа 39 program tur; var i, j, ii, jj, n, nn: integer; q: boolean; dx, dy:array[1..8] of integer; h:array[1..8,1..8] of integer; (*рекурсивная процедура - попытка сделать ход*) procedure try(i,x,у:integer; var q:boolean); var k, u, v: integer; ql: boolean; begin k:=0; repeat k:=k+l; ql:=false; u:=x+dx[k]; v:=y+dy(k]; if ( (1
<< | >>
Источник: А.В. Могилев Н.И. Пак Е.К. Хеннер. Информатика. 2003

Еще по теме 4.4. РЕКУРСИВНЫЕ АЛГОРИТМЫ:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. ЗАДАЧА: РЕШЕНИЕ