Результат функции рекурсивного поиска
До сих пор мы рассматривали варианты рекурсивных функций с логическим результатом. В этом случае производился поиск первого подходящего варианта. Причем данные самого варианта (например, путь к выходу из лабиринта) могли храниться в глобальных переменных. Если же допустимых вариантов несколько, то алгоритм несколько усложнится . Воспользуемся предыдущим примером для иллюстрации вносимых изменений .
Прежде всего, рекурсивная функция будет производить полный перебор возможных вариантов, без завершения по первому попавшемуся.
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, если слова не перекрываются
//------------------------------------------------------bk54-04.cpp
#include <iostream.h>
#include <string.h>
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);
str cat(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("");}
В Си++ для возврата рекурсивной функцией совокупности параметров можно использовать результата функции структурированную переменную, то есть возвращать структурированный тип по значению. В этом случае все проблемы по распределению памяти для временного хранения результата функции решаются транслятором. При этом в самой функции можно использовать операции присваивания структурированных переменных. В качестве примера рассмотрим вариант предыдущей программы, работающий со строкой ограниченной размерности, которая является элементом структуры.
//------------------------------------------------------bk54-05.cpp
#include <iostream.h>
#include <string.h>
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;}
