uzluga.ru
добавить свой файл


5.4. Рекурсия

Я оглянулся посмотреть, не оглянулась ли она, чтоб посмотреть, не оглянулся ли я...” М.Леонидов.

Рекурсивным называется способ построения объекта (понятия, системы), в котором определение объекта включает аналогичный объект в виде некоторой его части. Общеизвестный пример рекурсивного изображения - предмет между двумя зеркалами - в каждом из них виден бесконечный ряд отражений. Такой же несерьезный пример - детская считалка:


...

У попа была собака, он ее любил.

Она съела кусок мяса, он ее убил.

Камнем придавил, и на камне написал:

У попа была собака...


Более серьезные примеры рекурсии можно обнаружить в программировании:

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

- рекурсивная структура данных - элемент структуры данных содержит один или несколько указателей на такую же структуру данных. Например, односвязный список можно определить как элемент списка, содержащий указатель NULL или указатель на аналогичный список;

- рекурсивная функция -тело функции содержит прямой или косвенный (через другую функцию) собственный вызов.

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

Особенности программирования рекурсивных функций

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


.void main() void F() void F() void F()

{ { { {

F(); ..if()F(); ...if()F(); ...if()F();

} } } }


На самом деле этот эффект воспроизводится в компьютере. Однако копируется при этом не весь текст функции (не вся функция), а только ее части, связанные с данными (формальные, фактические параметры, локальные переменные и точка возврата). Алгоритм (операторы, выражения) рекурсивной функции не меняется, поэтому он присутствует в памяти компьютера в единственном экземпляре.

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

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

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

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

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


Из сказанного следует, что формальные параметры рекурсивной функции, внешние и локальные переменные не могут быть взаимозаменяемы, как это иногда делается в обычных функциях. Кроме того, каждый новый рекурсивный вызов порождает новый "экземпляр" формальных параметров и локальных переменных, причем старый "экземпляр" не уничтожается, а сохраняется в стеке по принципу вложенности. Здесь имеет место единственный случай, когда одному имени переменной в процессе работы программы соответствуют несколько ее "экземпляров". Рассмотрим подробнее этот парадокс. Как уже было сказано, рекурсивный вызов функции внешне выглядит как создание в программе ее копии. В действительности же алгоритмическая компонента функции не копируется, а создается копия только с ее локальных данных. Происходит это в такой последовательности:

- в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров. Обычно это производится в порядке, обратном их следованию в списке;

- при вызове функции в стек записывается точка возврата - адрес той части программы, где находится вызов функции;

- в начале тела функции в стеке резервируется место для локальных (автоматических) переменных.

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

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

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

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

Философские аспекты рекурсии

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

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

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

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

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

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

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

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

Линейная рекурсия

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


// Рекурсивный алгоритм

int fact(int n)

{

if (n==1) return 1;

return n * fact(n-1);

}

// Циклический алгоритм

int fact(int n)

{

for (int s=1; n!=0; n--) s *=n;

return s;

}

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

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

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

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

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

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

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

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

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

-выбранный элемент записывается в область глобальных данных, в которых моделируется стек для возврата результата;

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

Все перечисленные принципы так и останутся пустым звуком, если их не проиллюстрировать на примерах рекурсивных программ.

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

С точки зрения математики лабиринт представляет собой граф, а алгоритм поиска выхода из него - производит поиск пути, соединяющего заданные вершины. Однако в данном примере мы воспользуемся более простым, естественным представлением лабиринта. Зададим его в виде двумерного массива, в котором значение 1 будет обозначать “стенку”, а 0-“проход”.


int LB[10][10]={

{1,1,0,1,1,1,1,1,1,1},

{1,1,0,1,1,1,1,1,1,1},

{1,1,0,0,1,0,0,0,1,1},

{1,1,1,0,0,0,1,0,1,1},

{1,0,1,1,1,0,0,0,1,1},

{1,0,0,0,0,0,1,1,1,1},

{1,1,1,1,1,0,1,1,1,1},

{1,1,1,1,1,0,0,0,1,1},

{1,1,1,1,1,1,1,1,1,1},

{1,1,1,1,1,1,1,1,1,1}};


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


void step(int x,int y)

{

step(x+1,y);...

step(x,y+1);...

step(x-1,y);...

step(x,y-1);...

}

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


int step(int x,int y)

{...

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

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

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

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

return 0;

}

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


int step(int x,int y)

{...

if (step(x+1,y)) { LB[x][y]=2; return 1;}

if (step(x,y+1)) { LB[x][y]=2; return 1;}

if (step(x-1,y)) { LB[x][y]=2; return 1;}

if (step(x,y-1)) { LB[x][y]=2; return 1;}

return 0;

}

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


int step(int x,int y)

{

if (LB[x][y]==1) return 0;

if (x==0 || x==9 || y==0 || y==9) return 1; ...

И, наконец, последнее ограничение. Естественно, что алгоритм не должен возвращаться в ту точку, из которой он только что пришел. Отсюда естественное желание - передавать на вход функции и координаты “предыдущей” точки. Но это не дает гарантии от зацикливания. Так, если в лабиринте есть замкнутые пути, то зацикливание произойдет, даже если помнить предыдущую точку. Выход - в отметке всех пройденных точек лабиринта. Но при этом следует заметить, что каждая точка отмечается только на время рекурсивного вызова, если эти вызовы дают отрицательный результат, то отметка снимается. Предлагаемый ниже вариант с отметками пройденных точек, кроме всего прочего, сохраняет отмеченным путь, который ведет к выходу из лабиринта


//------------------------------------------------------------ bk541.cpp

int step(int x,int y)

{

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

if (x==0 || x==9 || y==0 || y==9) return 1; // края

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

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

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

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

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

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

return 0;

}

Обход шахматной доски

В качестве примера рассмотрим проектирование функции для поиска последовательности обхода конем шахматной доски.


Шаг 1. Алгоритм обхода можно разбить на последовательность шагов. Каждый шаг характеризуется начальным состоянием - текущим положением коня. Алгоритм на каждом шаге предполагает проверку возможности сделать ход в каждом из 8 допустимых направлений. Схема алгоритма имеет вид:


void step(int x0, int y0)

{ // формальные параметры -

// текущая позиция коня

// приращения координат для 8 ходов

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

{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}

};

int i; // локальный параметр - номер хода

if (x < 0 || x >=7 || y < 0 || y >=7 )

return; // выход за пределы доски

for (i=0; i<8; i++)

step(x0+xy[i][0], y0+xy[i][1]);

// выполнить следующий ход

}


Шаг 2. Предыдущий шаг дает полный перебор возможных последовательностей ходов коня. Функция имеет результат void, то есть является безусловной. Далее необходимо определить, как производить выбор необходимой последовательности. Очевидно, функция должна давать логический результат - 0, если при выполнении очередного хода в данном направлении задача не решается и 1, если решается успешно. При этом цикл, в котором происходит рекурсивный вызов - просмотр очередных ходов, выполняется до первого успешного вызова:


int step(int x0, int y0)

{

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

{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}

};

int i; // локальный параметр - номер хода

if (x < 0 || x >=7 || y < 0 || y >=7 )

return(0); // выход за пределы доски

for (i=0; i<8; i++)

if (step(x0+xy[i][0], y0+xy[i][1]))

return(1); // поиск успешного хода

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

}


Шаг 3. Далее необходимо определить условия начала и завершения рекурсивного процесса, а также условия взаимодействия шагов между собой. Условием завершения процесса является обход всех 64 полей доски. При этом не должно производиться повторное попадание на то же самое поле. Тогда необходимо фиксировать количество пройденных полей и отмечать пройденные. Это можно сделать только используя внешние переменные, так как они проверяются на разных шагах рекурсии. Номер шага будем использовать также для отметки поля. По завершению программы массив полей будет содержать номера шагов коня.


//--------------------------------------------- bk542.cpp

//------Обход шахматной доски конем

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

int nstep; // номер шага

int step(int x0, int y0)

{

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

{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}

};

int i; // локальный параметр - номер хода

if (x0 < 0 || x0 >=7 || y0 < 0 || y0 >=7 )

return(0); // выход за пределы доски

if (desk[x0][y0] !=0)

return(0); // поле уже пройдено

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

if (nstep == 64)

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

for (i=0; i<8; i++)

if (step(x0+xy[i][0], y0+xy[i][1]))

return(1); // поиск успешного хода

nstep--; // вернуться на ход назад

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

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

}

void Path(int x0, int y0)

{

int i,j; // очистка доски

for (i=0; i<8; i++)

for (j=0; j<8; j++) desk[i][j] =0;

nstep = 1; // установить номер шага

step(x0,y0); // вызвать функцию для исходной

} // позиции


Линейный кроссворд

Для заданного набора слов требуется построить линейный кроссворд. Если окончание одного слова совпадает с началом следующего более чем в одной букве (например, МАТРАС-РАСИСТ), то такие слова можно объединить в цепочку. Первоначально ставится задача - получить любую такую цепочку, окончательно - цепочку минимальной длины.

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

- рекурсивная функция выполняет попытку присоединения очередного слова к уже выстроенной цепочке;

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

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

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

Для представления множества слов будем использовать массив указателей на строки. Исключение строки из множества будет заключаться в установке указателя на строку нулевой длины. Теперь можем “набросать” общий вид рекурсивной функции


char *w[]={"РАСИСТ","МАТРАС","МАСТЕР","СИСТЕМА","СТЕРВА",

NULL}; // Множество слов - глобальные данные


int step(char *lw) // параметр - текущее слово цепочки

{ int n; // результат - можно присоединить

// оставшиеся

// проверка условия завершения рекурсии

// - все слов из w[] присоединены

for (n=0; w[n]!=NULL;n++)

{ // проверка на присоединение

char *pw; // очередного слова

if (*w[n]==0) continue;

pw=w[n]; // пустое слово - пропустить

w[n]=""; // исключить проверяемое слово из

// множества

{ // попытка присоединить слово

if (step(pw)) // - рекурсивный вызов

{ ...

return 1; // удача - завершить успешно

}

}

w[n]=pw; // возвратить исключенное слово

} // неудача - нельзя присоединить

return 0; // ни одного слова

}

Данный “набросок” не содержит некоторых частностей, которые не меняют общей картины:

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

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

сама цепочка выбранных слов выводится в процессе “ретрансляции” положительного результата непосредственно на экран в обратном порядке (что не совсем “красиво”). В принципе она может быть сформирована и в глобальных данных.


//------------------------------------------------ bk543.cpp

#include

#include

char *w[]={"РАСИСТ","МАТРАС","МАСТЕР","СИСТЕМА","СТЕРВА",

NULL};


int step(char *lw) // параметр - текущее слово цепочки

{ int n;

for (n=0; w[n]!=NULL;n++)

if (*w[n]!=0) break;

if (w[n]==NULL) // цепочка выстроена, все слова

return 1; // из w[] присоединены

for (n=0; w[n]!=NULL;n++)

{ // проверка на присоединение

char *pw; // очередного слова

if (*w[n]==0) continue;

pw=w[n]; // пустое слово - пропустить

w[n]=""; // исключить проверяемое слово из

if (TEST(lw,pw)) // множества

{ // попытка присоединить слово

if (step(pw)) // присоединено - попытка вывести

{ // цепочку из нового слова,

cout << pw << "\n";

return 1; // удача - вывести слово и выйти

}

}

w[n]=pw; // возвратить исключенное слово

}

return 0;

}

Чисто технические детали: функция TEST проверяет, не совпадает ли окончание первой строки с началом второй путем обычного сравнения строк при заданной длине “хвоста” первой строки.


int TEST(char *s, char *r)

{ int n,k;

n=strlen(s);

if (n==0) return 1;

for (;*s!=0 && n>1; s++,n--)

if (strncmp(s,r,n)==0) return 1;

return 0; }

Другая техническая проблема - удобство первоначального запуска рекурсии. Функция TEST при первом параметре - пустой строке возвращает ИСТИНУ при любом виде второй строки. Этого достаточно, чтобы запустить первый шаг рекурсии. При наличии пустой строки в качестве параметра функции step на первом шаге рекурсии будет производиться безусловная проверка каждого слова на предмет создания цепочки.


void main() { step(""); }

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

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

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


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.


char *step(char *lw)// результат - строка с цепочкой слов

{ ... // параметр - слово, с которого

// начинается цепочка

for (n=0; w[n]!=NULL;n++) //просмотр оставшихся слов

{

char *pw,*pp; int l; // слово уже выбрано -

if (*w[n]==0) continue; // пропустить

if ((l=TEST(lw,w[n]))!=-1)

// можно присоединить к текущему

{

pw=w[n]; //убрать очередное слово из списка

w[n]=""; //рекурсивный вызов для нового

if ((pp=step(pw))!=NULL)

{ // !=NULL - цепочка выcтроена

s=new char[l+strlen(pp)];

strcpy(s,lw); // присоединить текущее слово

strcpy(s+l,pp);// к началу и использовать как

delete pp; // новый результат

}

w[n]=pw;

}

}...}

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


smin=NULL;

for (n=0; w[n]!=NULL;n++)

{ ...if ((pp=step(pw))!=NULL)

{

s=... //сформировать очередной результат

delete pp;//запоминание самой короткой строки

if (smin==NULL) smin=s; else

if (strlen(smin)>strlen(s))

{ delete smin; smin=s; }

}

}

return smin;

Окончательный вариант программы приведен ниже. Функция проверки “перекрытия ” слов возвращает количество “неперекрытых” букв в первом слове, 0 - если первое слово - пустая строка, либо -1, если слова не перекрываются


//---------------------------------------------- bk544.cpp

#include

#include

char *w[]={"bba","abb","ba",NULL};


int TEST(char *s, char *r)

{

int n,k;

k=n=strlen(s);

if (n==0) return 0;

for (;*s!=0 && n>0; s++,n--)

if (strncmp(s,r,n)==0)

return k-n;

return -1;

}


char *step(char *lw)

{ int n; char *s,*smin;

for (n=0; w[n]!=NULL;n++)

if (*w[n]!=0) break;

if (w[n]==NULL)

{

s=new char[strlen(lw)+1];

strcpy(s,lw);

return s;

}

smin=NULL;

for (n=0; w[n]!=NULL;n++)

{

char *pw,*pp; int l;

if (*w[n]==0) continue;

if ((l=TEST(lw,w[n]))!=-1)

{

pw=w[n];

w[n]="";

if ((pp=step(pw))!=NULL)

{

s=new char[l+strlen(pp)];

strcpy(s,lw);

strcat(s+l,pp);

delete pp;

if (smin==NULL) smin=s; else

if (strlen(smin)>strlen(s))

{ delete smin; smin=s; }

}

w[n]=pw;

}

}

return smin;

}


void main() { cout << step("");}


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


//------------------------------------------------------------ bk545.cpp

#include

#include

char *w[]={"bba","abb","ba",NULL};


int TEST(char *s, char *r)

{

int n,k;

k=n=strlen(s);

if (n==0) return 0;

for (;*s!=0 && n>0; s++,n--)

if (strncmp(s,r,n)==0) return k-n;

return -1;

}


#define SZ 80

struct string

{

int null; // Признак – строка пустая

char str[SZ]; // Строка ограниченной длины

};

string step(char *lw) // Функция возвращает структуру как результат

{ int n;

string s,smin; // Локальные переменные - структуры

for (n=0; w[n]!=NULL;n++)

if (*w[n]!=0) break;

if (w[n]==NULL) // Последняя строка

{ s.null=0; strcpy(s.str,lw); return s; }

smin.null=1; // Признак – строка еще пока пустая

for (n=0; w[n]!=NULL;n++)

{

char *pw; int l;

string pp; // Результат рекурсивного вызова

if (*w[n]==0) continue;

if ((l=TEST(lw,w[n]))!=-1)

{

pw=w[n];

w[n]="";

pp=step(pw); // Рекурсивная функция возвращает

if (!pp.null) // структурированную переменную

{ // За распределением памяти под

s.null=0; // структурированные переменные

strcpy(s.str,lw); // не следим

strcat(s.str,pp.str);

if (smin.null) smin=s; else

if (strlen(smin.str)>strlen(s.str))

smin=s; // Прямое присваивание структур

}

w[n]=pw;

}

}

return smin;

}

void main() { cout << step("").str;}