7.3. Технология проектирования рекурсивных алгоритмов

Специфика рекурсивных алгоритмов состоит в том, что они полностью исключают «исторический» подход к проектированию программы. Попытки логически проследить последовательность рекурсивных вызовов заранее обречены на провал. Их можно прокомментировать примерно такой фразой: «Функция F выполняет … и вызывает F, которая выполняет … и вызывает F…». Ясно, что для логического анализа программы в этом мало пользы. Более того, при ветвящейся рекурсии имеют место «откаты» этого процесса на предыдущие уровни рекурсии, то есть «исторически» следует рассуждать: «Функция F выполняет … и вызывает F, которая выполняет … и вызывает F…, после возврата из которой на предыдущий шаг снова вызывается F, которая выполняет …». Видимо, что здесь должно использовать рассуждения другого вида, более того, попытки «заглянуть» внутрь рекурсивного вызова должны пресекаться, ибо они автоматически приводят к вышеприведенным рассуждениям.

Инварианты рекурсивного алгоритма. Приведенный пример смутно напоминает нам попытки «исторического» анализа циклических программ. Там для того, чтобы объяснить результат выполнения цикла, предлагался некоторый инвариант (условие, соотношение), сохраняемое шагом цикла. Наличие такого инварианта позволяет «не заглядывать вперед» к последующим и «не оборачиваться назад» к предыдущим шагам цикла, ибо на них делается то же самое. Аналогичная ситуация имеет место в рекурсии. Только она усугубляется тем, что при ветвящейся рекурсии «исторический» подход вообще неприменим.

Рекурсивный алгоритм как процесс. Очевидно, что здесь придется «мыслить по-новому». Прежде всего, оставить традиционные подходы к достижению цели за один шаг и перейти от формулировок алгоритма в терминах «цели и средства» к формулировкам «возможные направления движения», приводящие к ней. Рекурсивный вызов, «экземпляр» рекурсивной функции является в этом случае одним из идентичных повторяющихся шагов некоторого процесса, который в целом и решает поставленную задачу. В терминах процесса и его шагов основные параметры рекурсивной функции получают дополнительный смысл:

• формальные параметры рекурсивной функции представляют начальное состояние для текущего шага процесса;

• фактические параметры рекурсивного вызова представляют начальное состояние для следующего шага, в который производится переход из текущего при рекурсивном вызове;

• локальные (автоматические) переменные представляют внутренние характеристики процесса на текущем шаге его выполнения;

• глобальные (внешние, статические) переменные представляют глобальное состояние всей системы, через которое отдельные шаги в последовательности могут взаимодействовать между собой.

Это значит, что формальные параметры рекурсивной функции, глобальные и локальные переменные не могут быть взаимозаменяемы, как это иногда делается в обычных функциях. Особо следует быть внимательным при работе с глобальными переменными, т.к. множество экземпляров рекурсивных вызовов фактически их разделяют. Если речь идет о поисковых алгоритмах, и в последовательности вызовов рекурсивных функций производятся изменения в глобальных переменных, то по возвращении из рекурсивного вызова необходимо возвратить значения этих переменных в исходное состояние, в котором они находились на этом шаге рекурсии, т.е. произвести «откат». Это объясняется тем, что смежные шаги рекурсивного алгоритма должны быть «прозрачны» по отношению друг к другу.

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

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

• для шага процесса – рекурсивного вызова, необходимо определить инварианты – сохраняемые в процессе выполнения алгоритма условия и соотношения;

• начальные условия очередного шага должны быть формальными параметрами функции;

• начальные условия следующего шага должны быть сформированы в виде фактических параметров рекурсивного вызова;

• локальными переменными функции должны быть объявлены все переменные, которые имеют отношение к протеканию текущего шага процесса и к его состоянию;

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

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

Итак, перечислим последовательность и содержание шагов в проектировании и «сведении вместе» фрагментов рекурсивной функции.

1. «Зацепить рекурсию» - определить, что составляет шаг рекурсивного алгоритма;

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

3. Глобальные переменные – общие данные процесса в целом;

4. Начальное состояние шага рекурсивного алгоритма – формальные параметры рекурсивной функции;

5. Ограничения рекурсии – обнаружение «успеха» - достижения цели на текущем шаге рекурсии и отсечение «неудач» - заведомо неприемлемых вариантов;

6. Правила перебора возможных вариантов – способы формирования рекурсивного вызова;

7. Начальное состояние следующего шага – фактические параметры рекурсивного вызова;

8. Содержание и способ обработки результата – полный перебор с сохранением всех допустимых вариантов, первый возможный, оптимальный;

9. Условия первоначального вызова рекурсивной функции в main.

Результат рекурсивного алгоритма. Особенность рекурсивного программирования состоит в том, что цель рекурсивного алгоритма не определяется явным образом. Наоборот, задаются только возможные направления движения к ней («цель – ничто, движение - все»). Поэтому на каждом шаге рекурсивного алгоритма возможны три варианта:

1. цель достигнута (положительный результат) - завершение цепочки (но только именно этой) рекурсивных вызовов;

2. в данном направлении движение к цели невозможно (отрицательный результат) - завершение цепочки рекурсивных вызовов;

3. движение может быть продолжено – рекурсивные вызовы для следующего шага.

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

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

//--------------------полный перебор возможных решений
void F() {
  if (тупик) return;

  if (успех) {
    вывести решение или сохранить
    return;

  }

  for (i = 0; i < n; i++)
    if (…) F();
}

2. Рекурсивная функция выполняет поиск первого попавшегося успешного варианта. Ее результатом обычно является логическое значение. При этом истина соответствует успешному завершению поиска, а ложь - неудачному. Общая для всех алгоритмов схема: если рекурсивный вызов возвращает истину, то она должна быть немедленно «передана наверх», то есть текущий вызов также должен быть завершен со значением истина. Если рекурсивный вызов возвращает ложь, по поиск должен быть продолжен. При завершении полного перебора всех вариантов рекурсивная функция также должна возвратить ложь. Характеристики оптимального варианта могут быть возвращены в глобальных данных, либо по ссылке. В Си++ аналогичный результат можно возвратить при помощи исключения, которое приводит к цепочке возвратов из функции до обработчика (см. последующие примеры).

//--------------------поиск первого подходящего решения
int F() {
    if (тупик) return 0;

    if (успех) {
      вывести решение или сохранить
      return 1;

    }

    for (i = 0; i < n; i++)
      if (…) {
        if (F() == 1) return 1; // трансляция предыдущего «успеха»
        return 0;
      }
}

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

Способы и направление накопления результата рекурсивного алгоритма. С процессом движения по цепочке рекурсивных вызовов могут быть связаны определенные характеристики рекурсивного процесса в целом (например, длина пройденного пути, количество выбранных элементов и т.п.). Их можно естественным образом «накапливать» в формальных параметрах рекурсивной функции:

//--------------------Накопление характеристик рекурсивного процесса

// n– количество пройденных «городов», lnt – длина пути, k-текущий «город»

void F(int n, int lnt, int k) {
  if (уже были) return;

  if (n == N) { // обошли все «города»
    вывести lnt или сохранить
    return;
  } // рекурсия для соседних

  for (i = 0; i < N; i++)
    if (…) F(n + 1, lnt + S[k][i], i);
}

В этом фрагменте длина пройденного пути накапливается в формальном параметре lnt, фактический параметр следующего рекурсивного вызова увеличивается на расстояние до «соседа» - lnt+S[k][i].

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

//--------------------Сохранение оптимального варианта в глобальных данных

// n– количество пройденных «городов», lnt – длина пути, k-текущий «город»

int lntmin = -1; // начальное значение минимального пути

void F(int n, int lnt, int k) { // -1 – поиск первого решения
    if (уже были) return;

    if (n == N) { // обошли все «города»
      if (lntmin == -1 || lnt < lntmin) { // первое или более
        lntmin = lnt; // оптимальное решение
        return;
      } // рекурсия для соседних

      for (i = 0; i < N; i++)
        if (…) F(n + 1, lnt + S[k][i], i);
    }
}

Прямое накопление результат можно производить и в глобальных данных. В нашем примере это может быть последовательность «пройденных городов». Но здесь нужно помнить о необходимости «отката» - возвращении глобальных данных в исходное состояние при завершении шага рекурсии.

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

//--------------------Обратное накопление результата рекурсивной функцией

// n– количество пройденных «городов», k-текущий «город»

// Функция возвращает длину пройденного пути от текущего «города» до цели

int F(int n, int k) { // -1 – цель не достигнута, путь не найден

  if (уже были) return -1;

  if (n == N) return 0; // обошли все «города» - начало накопления

  int vmin = -1; // минимальный путь с учетом себя

  for (i = 0; i < N; i++) {

    int v = F(n + 1, i); // получен путь от соседнего до цели

    if (v == -1) continue; // нет пути – пропустить

    v = v + S[k][i]; // скорректировать с учетом пути до соседа

    if (vmin == -1 || v < vmin) // запомнитьминимальный

      vmin = v;

  }

  return vmin;
}

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

Рекурсия и математическая индукция. Принцип программирования рекурсивных функций имеет много общего с методом математической индукции. Напомним, что этот метод используется для доказательства корректности утверждений для бесконечной последовательности состояний, а именно: если утверждение верно в начальном состоянии, а из его справедливости в n состоянии можно доказать его справедливость в n+1, то такое утверждение будет справедливым всегда. Этот принцип и применяется при разработке рекурсивных функций: сама рекурсивная функция представляет собой переход из n в n+1 состояние некоторого процесса. Если этот переход корректен, то есть соблюдение некоторых условий на входе функции приводит к их соблюдению на выходе (то есть в рекурсивном вызове), то эти условия будут соблюдаться во всей цепочке состояний (при безусловной корректности начального). Отсюда следует, что самое важное в определении рекурсии - выделить те условия (инварианты), которые соблюдаются (сохраняются) во всех точках процесса и обеспечить их справедливость от входа в рекурсивную функцию до ее рекурсивного вызова. При этом «категорически не приветствуется» заглядывать в следующий шаг рекурсии или интересоваться состоянием процесса на предыдущем шаге. Да и в этом нет необходимости с точки зрения приведенного здесь метода доказательства.

Проектирование рекурсивных алгоритмов и заповеди христианства. В Нагорной проповеди Нового Завета Иисус высказал одну из заповедей блаженства: «будьте как птицы небесные, не заботьтесь о завтрашнем дне, пусть он заботится сам о себе». Сама по себе эта фраза, вырванная из контекста и принятая без должного размышления, сильно смахивает на обыкновенный «пофигизм»: живите сегодняшним днем, а после нас - хоть потоп. На самом же деле смысл ее, как руководства к действию, прямо противоположен: если хочешь в жизни достичь благодати, будь достоин сегодняшнего для, не объясняй своих слабостей прошлым, не уповай на исправление сегодняшних ошибок в будущем. Сосредоточься на сегодняшнем дне, и тогда цель в будущем будет достигнута сама собой. То же самое - и в проектировании рекурсивной функции: следует сосредоточить внимание на текущем шаге рекурсии, не заботясь о том, когда она была вызвана и что будет делать следующий ее шаг: на самом деле они будут делать то же самое, что и текущий (хотя и не написанный). Если «сегодняшний» вызов функции корректен и все ее действия приводят к такому же корректному вызову ее «завтра», то цель рано или поздно будет достигнута.

Рекурсия и «буржуазный ревизионизм». Если довести до абсолюта принципы проектирования рекурсивных алгоритмов, то получим известный лозунг буржуазных экономистов, так беспощадно раскритикованных в свое время В.И. Лениным: «Цель – ничто, движение все» (Бернштейн). Все-таки в этом лозунге есть разумное зерно, хотя бы для программистов.

Бернштейн Эдуард (1850— 1932 гг.) — один из лидеров германской социал-демократии, идеолог реформизма. Во 2-й половине 1890-х гг. выступил с критикой теоретических основ марксизма. Бернштейн отвергал научное обоснование социализма, который считал этическим идеалом; выдвинул программу реформ капитализма и компромиссов с буржуазией («Конечная цель — ничто, движение — всё»).

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

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

Пусть требуется «развернуть» текстовую строку, в которой повторяющиеся фрагменты заключены в скобки, а после открывающейся скобки может находиться целая константа, задающая число повторений этого фрагмента в выходной строке. Например: «aaa(3bc(4d)a(2e))aaa» разворачивается в «aaabcddddaeebcddddaeebcddddaeeaaa».

1. Шаг рекурсии – отработка заключенного в скобках фрагмента. Инвариант рекурсии – функция получает указатель на первый за скобкой символ фрагмента и должна при рекурсивном вызове передать такой же указатель на вложенный фрагмент.

void step(char *p) {
  … 
  if (*p==’(‘) {
    p++; 
    step(p);
  }
}

2. Результат работы – сгенерированная строка – может быть глобальным массивом. В процессе ее заполнения необходим также глобальный указатель, которым будут пользоваться все рекурсивные вызовы. Более естественно передать его всем через ссылку. Отсюда имеем окончательный список параметров.

void step(char * p, char * & out) {
  …
  if (*p == ’(‘) {
    p++;
    step(p, out);
  }
}

3. Шаг рекурсии состоит в извлечении целой константы – счетчика повторений. Затем внешний цикл производит заданное количество повторений, а внутренний – переписывает символы текущего фрагмента из входной строки в выходную, пока не встретит конца фрагмента (символ ‘)’ или конец строки – «защита от дурака» и первоначальный вызов).

void step(char * p, char * & out) {

  for (int n = 0;
    while ( * p >= ’0’ && * p <= ’9’) // Накопление константы

      n = n * 10 + * p++ - ‘0’;

    if (n == 0) n = 1; // При отсутствии – n=1

    while (n-- != 0) { // Цикл повтора фрагмента

      for (char * q = p;* q != 0 && * q != ’)’;
      q++) {

      if ( * q != ’)’) // Цикл посимвольного копирования

    *
    out++ = * q; // Все, кроме ‘(‘ – копировать

    else {

      q++; // Пропустить ‘( ‘

      step(q, out); // Рекурсия для вложенного фрагмента

    }
  }
}

4. Необходимо еще раз обратить внимание на инвариант процесса – каждый шаг должен «брать на себя» текущий фрагмент и, соответственно, передавать рекурсивным вызовам вложенные фрагменты. Но отсюда следует, что сам он должен «пропускать» эти фрагменты при своем выполнении. Между вызываемой и вызывающей функцией должна быть «обратная связь» по результату: каждый рекурсивный вызов должен возвращать указатель, продвинутый по входной строке на просмотренный фрагмент. С учетом тонкостей пропуска закрывающихся скобок получим окончательный вариант.

//------------------------------------------------------73-01.cpp

//---- Генерация вложенных повторяющихся фрагментов

char * step(char * p, char * & out) {

  int n = 0;
  char * q;

  while ( * p >= '0' && * p <= '9') // Накопление константы

    n = n * 10 + * p++ - '0';

  if (n == 0) n = 1; // При отсутствии n=1

  while (n-- != 0) { // Цикл повтора фрагмента

    for (q = p;* q != 0 && * q != ')'; q++) {

      if ( * q != '(') // Цикл посимвольного копирования

        *
        out++ = * q; // Все, кроме ( копировать

      else {

        q++; // Пропустить (

        q = step(q, out); // Рекурсия для вложенного фрагмента

      }

    }
  }

  if ( * q == ')') q++;
  return q;
}

5. В заключение необходимо проверить условия первоначального вызова. Если передать на вход функции любую строку, не начинающуюся с целой константы, то она будет считать всю ее повторяющимся фрагментом с числом повторов, равным 1. Это обеспечат сделанные нами добавления - n=1 при отсутствии константы и завершение по концу строки.

void main() {
  char s[80],*ps=s; 
  step("aaa(2b(3cd)b)aaa",ps); 
  *ps=0; 
  puts(s); 
}

Задача о восьми ферзях. Расположить 8 ферзей на шахматной доске так, чтобы они не находились друг у друга «под боем».

1. Поскольку ферзи «бьют» друг друга по вертикали (то есть на каждой вертикали их не более одного), то шаг рекурсии может состоять в выставлении ферзя на очередную вертикаль. Инвариант процесса – первые i-1 ферзей уже корректно выставлены, шаг добавляет еще одного ферзя, сохраняя корректность. Формальный параметр шага – номер вертикали (i), фактический параметр рекурсивного вызова – номер следующей вертикали (i+1). Алгоритм ищет первую подходящую расстановку и возвращает логическое значение – расстановка найдена (1) или не найдена (0). Общие данные представляют собой доску с уже выставленными ферзями: для этого достаточно иметь одномерный массив, индекс в котором обозначает позицию ферзя по вертикали, а значение – позицию по горизонтали.

int R[8];

int step(int i) { … step(i+1);…}

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

int R[8];

int step(int i) {
  for (int j = 0; j < 8; j++) {
    R[i] = j;

    if (!TEST(i)) continue; // Под боем - пропустить

    if (step(i + 1)) return 1; // Цепочка достроена последующими шагами - выйти
  }
  return 0; // Цикл завершен нормальным образом - неудача
} 

3. Поскольку каждый ферзь «выставляется» в глобальном массиве, то по завершении цепочки «успешных» выходов из рекурсивных вызовов в нем и будет находиться первый подходящий вариант. И, наконец, последние штрихи. В рекурсивной функции, «ретранслирующей успех» от вызываемой функции к вызывающей нет первопричины этого «успеха». Ферзи считаются успешно выставленными, если рекурсивная функция достигает несуществующей вертикали. Эта проверка должны быть сделана в самом начале тела функции. Функция TEST проверяет нахождение i-го со всеми предыдущими ферзями на одной горизонтали и диагонали. Первоначально функция вызывается для i=0.

//------------------------------------------------------73-02.cpp

//------- Задача о восьми ферзях

int R[8];

int TEST(int i) {

  for (int j = i - 1; j >= 0; j--) {

    if (R[i] == R[j]) return 0; // По горизонтали

    if (abs(R[i] - R[j]) == i - j) return 0; // По диагонали

  }

  return 1;
}

int step(int i) {
  if (i == 8) return 1;

  for (int j = 0; j < 8; j++) { // Перебор по вертикали
    R[i] = j;

    if (!TEST(i)) continue; // Под боем - пропустить

    if (step(i + 1)) return 1; // Цепочка достроена - выйти
  }

  return 0; // Цикл завершен - неудача
} 

void main() {
  step(0);
  for (int i = 0; i < 8; i++) printf("%d  ", R[i]);
  printf("\n");
}

Поиск выхода в лабиринте. С точки зрения математики лабиринт представляет собой граф, а алгоритм поиска выхода из него - производит поиск пути, соединяющего заданные вершины. Чтобы более наглядно продемонстрировать особенности рекурсивного программирования, будем использовать более «образное» представление лабиринта в виде двумерного символьного массива.

xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxxxxxxxx
x x              x      x x              x
x x xxxxxxxxxxx  x      x x xxxxxxxxxxx  x
x x   x          x      x x   x          x
x     x  xxx x xxx      x     x  xxx x xxx
x xxxxxx x   x   O      x xxxxxx x...x...O
x          x   x x      x..........x...x x
x xxxxxxxxxx xxx x      x.xxxxxxxxxx xxx x
x   x   x    x   x      x...x   x    x   x     
xxx xxx xxx xxx xx      xxx.xxx xxx xxx xx     
x    x  x   x x xx      x  . x  x   x x xx
xxx xxx x xxx x xx      xxx.xxx x xxx x xx
x    I  x   x   xx      x  ...  x   x   xx
xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxxxxxxxx

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

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

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

//------------------------------------------------------73-03.cpp

// Поиск выхода из лабиринта

char LB[N][N];

int step(int y, int x) {

  if (LB[y][x] == 'O') return 1; // выход найден

  if (LB[y][x] != ' ') return 0; // стенки и циклы

  LB[y][x] = '.'; // отметить точку

  if (step(y + 1, x)) return 1; // четыре возможных направления движения

  if (step(y, x + 1)) return 1;

  if (step(y - 1, x)) return 1;

  if (step(y, x - 1)) return 1;

  LB[y][x] = ' '; // снять отметку

  return 0;
}

Задача о зеркалах. В комнату через одно «окно» попадает луч света, который, последовательно отражаясь от нескольких зеркал, выходит через другое. Зеркала могут быть повернуты под углом +45 или –45 градусов. Местоположение зеркал известно, необходимо «повернуть» их должным образом.

Программа моделирует движение луча, используя естественное представление данных в двумерном символьном массиве. Пока моделируется движение луча без отражения (в том числе пересечение его со «стеной»), явная необходимость в рекурсии не возникает. В момент пересечения с еще не сориентированным зеркалом возникает необходимость проверить два возможных варианта его отражения – в этом случае используется ветвящаяся рекурсия. В остальных случаях линейная рекурсия поддерживает принятый стиль программирования:

• шаг рекурсии – распространение луча с заданными координатами (x,y) и направлением распространения (dx,dy);

• при отсутствии препятствий движение луча моделируется через приращение координат в заданном направлении x+dx, y+dy, пройденные позиции отмечаются символом «точка» - таким образом луч «оставляет» след, который стирается по возвращении из цепочки рекурсивных вызовов;

• достижение «выхода» приводит к принудительному завершению последовательности вызовов через исключение, пройденный путь естественным образом сохраняется;

• при обнаружении в текущей точке зеркала рекурсивный вызов происходит дважды: для каждого из возможных поворотов, изменение направления движения луча моделируются достаточно просто – обменом приращений dx и dy и сменой их знаков;

• сама постановка задачи исключает «зацикливание» луча, однако он может отразиться от уже сориентированного зеркала с обратной стороны, при этом уже установленная ориентация зеркала не меняется.

xxxxIxxxxxxxxxxxxxxx    xxxx.xxxxxxxxxxxxxxx
x                  x    x   .              x
x   *     *   *    x    x   \.....\   *    x
x                  x    x         .        x
x                  x    x         .        x
x   *     *   *    x    x   *     \...\    x
x                  x    x             .    x
x                  x    x             .    x
x   *         *    O    x   *         \....O
x                  x    x                  x
xxxxxxxxxxxxxxxxxxxx    xxxxxxxxxxxxxxxxxxxx

//------------------------------------------------------74-04.cpp

//------ Комната с зеркалами ("луч света в темном царстве")

#define N 100

char LB[N][N];

// Рекурсивная функция - текущие координаты (x,y) и приращения (dx,dy)

int step(int y, int x, int dy, int dx) {

  int c;

  switch (LB[y][x]) { // поиск первого подходящего варианта

  case 'O':
    throw 1; // найден выход - прервать обход (исключение)

  case ' ':
    LB[y][x] = '.'; // свободное пространство - двигаться в прежнем

    step(y + dy, x + dx, dy, dx); // направлении с отметкой пройденного пути

    LB[y][x] = ' '; // если вернулись - очистить отмеченный путь

    break;

  case '.':
    LB[y][x] = '+'; // пересечение с лучом (в перепендикулярном

    step(y + dy, x + dx, dy, dx); // направлении - аналогично предыдущему

    LB[y][x] = '.';

    break;

  case '*':
    LB[y][x] = '\\'; // неориентированное зеркало -

    c = dx;
    dx = dy;
    dy = c; // два варианта ориентации с

    step(y + dy, x + dx, dy, dx); // соответствующей сменой направления

    dx = -dx;
    dy = -dy; // движения луча.

    LB[y][x] = '/';

    step(y + dy, x + dx, dy, dx); // если вернулись - восстановить

    LB[y][x] = '*'; // "неориентированное зеркало"

    break;

  case '\\':
    c = dx;
    dx = dy;
    dy = c; // отражение от ориентированного зеркала

    step(y + dy, x + dx, dy, dx); // (с обратной стороны)

    break; // - один вариант распространения луча

  case '/':
    c = dx;
    dx = dy;
    dy = c;

    dx = -dx;
    dy = -dy;

    step(y + dy, x + dx, dy, dx);

    break;

  }
  return 0;
}

Обход конем шахматной доски. Приведенных выше примеров вполне достаточно, чтобы проиллюстрировать следующим формальным перечислением принятых решений:

• шаг процесса – выставление коня на очередную клетку доски с заданными координатами;

• рекурсивная функция делает 8 попыток движения конем на соседние клетки, используется массив относительных смещений;

• формальным параметром функции является номер шага: он используется для определения условий достижения «успеха» - пройдены все клетки доски;

• доска – глобальный двумерный массив, при «прохождении» коня клетка заполняется номером шага алгоритма, этим сохраняется последовательность ходов при достижении успеха, это же является защитой от повторных прохождений той же самой клетки;

• реализован алгоритм поиска первого подходящего варианта;

• ограничения рекурсии – выход за пределы доски, повторный обход отмеченной (пройденной) клетки.

//------------------------------------------------------73-05.cpp
//------Обход шахматной доски конем
#define N 5

int desk[N][N];  // поля доски

int step(int x0, int y0, int nstep) {  // nstep - номер шага

  static int xy[8][2] = {{1, -2}, {1, 2}, {-1, -2}, {-1, 2},
                         {2, -1}, {2, 1}, {-2, 1},  {-2, -1}};

  if (nstep == N * N) return 1;  // все поля отмечены - успех

  if (x0 < 0 || x0 >= N || y0 < 0 || y0 >= N)
    return 0;  // выход за пределы доски

  if (desk[x0][y0] != 0) return 0;  // поле уже пройдено

  desk[x0][y0] = nstep + 1;  // отметить свободное поле

  for (int i = 0; i < 8; i++)  // локальный параметр - номер хода
    if (step(x0 + xy[i][0], y0 + xy[i][1],
             nstep + 1))  // рекурсивный вызов для следующего хода
      return 1;  // поиск успешного хода

  desk[x0][y0] = 0;  // стереть отметку поля

  return 0;
}  // последовательность не найдена

void main() { 
  step(0, 0, 0); // вызвать функцию для исходной позиции 
}