7.5. Рекурсия, стек, очередь

7.5. Рекурсия, стек, очередь Рекурсия и стек. Каждый шаг рекурсии представляет собой независимый алгоритм (отдельный «экземпляр» функции). В случае ветвящейся рекурсии один такой алгоритм порождает несколько подобных, поскольку все они выполняются на одном процессоре, возникают «отложенные шаги», которые необходимо выполнить «потом». Возникает вопрос, а где, собственно, говоря, сохраняются данные об этих отложенных шагах. В случае использования обычной рекурсии само текущее состояние алгоритма, его локальные данные (например, индекс цикла перебора вариантов) и задают поведение текущего шага рекурсии «в будущем». При рекурсивном вызове это состояние запоминается в стеке, при возвращении – автоматически продолжает текущий шаг от точки «замерзания». Но то, что делается автоматически, можно реализовать в явном виде с использованием специально организованного программного стека, если помещать в него набор данных, соответствующих начальному состоянию каждого следующего шага. Тогда рекурсивный алгоритм становится простым циклическим.

//-------------------------------------------------------------------75-00.cpp

// Схема рекурсивного алгоритма с явным стеком

stack S; // Явный стек

data D0={…}; // Начальное состояние – первый шаг

S.push(D0); // Поместить в стек

while(S.size()!=0){ // Цикл извлечения шагов из стека

        data D=S.pop();                         // Извлечь из стека данные нового шага

        …                                             // Очередной шаг

        if (тупик) continue;

        if (успех) break;

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

                    {

                    data D1;

                    D1=…                           // Данные нового шага

                    S.push(D1);                   // сформировать и поместить в стек

                    }          

}

В целом такое решение является более громоздким, нежели явная рекурсия. Прежде всего, потому, что в стеке требуется сохранять все данные, касающиеся начального состояния следующего шага. Кроме того, если рекурсивная функция содержит некоторый завершающий фрагмент кода после рекурсивных вызовов, то он также должен быть «отложен» в стек. В качестве примера рассмотрим уже известное решение задачи о лабиринте (см. 5.3). На каждом его шаге рассматривается возможность движения через очередную точку («не стена» и не повторное прохождение), и при положительном решении производится отметка этой точки и попытка движения в 4 соседние. При явном использовании стека на каждом шаге цикла из стека извлекается очередная точка (struct XY) и в стек записываются координаты 4-х соседних точек. Поскольку завершающим фрагментом рекурсивной функции является снятие отметки с пройденной точки, то данные об этом отложенном действии также надо занести в стек. Для этого в struct XY вводится дополнительный признак last.

//------------------------------------------------------75-01.cpp

// Задача о лабиринте – явный стек

struct XY{ // x,y – координаты точки

        int x,y,last;                                // last – признак «последнего» шага

        XY(int x0,int y0,int last0=0) { x=x0,y=y0,last=last0; }

        XY(){ x=y=last=0; }

        };

stack<XY,100> S; // Явный стек

XY A(5,5);

void main(){

S.push(A); // Поместить в стек

int found=0; // Признак завершения

while(S.size()!=0){ // Цикл извлечения шагов из стека

        XY D=S.pop();                           // Извлечь из стека данные нового шага

        if (D.last==1){

                    LB[D.x][D.y]=0;             // "последний" вариант - снять отметку

                    continue;

                    }

        if (D.x<0 || D.x>9 || D.y<0 || D.y>9)

                    {found=1; break; }           // Достигли края - выйти из цикла

        if (LB[D.x][D.y]!=0)

                    continue;                       // стенки и повторы – завершить шаг

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

        S.push(XY(D.x,D.y,1));               // вариант для "завершения" шага рекурсии

        S.push(XY(D.x+1,D.y,0));           // варианты для соседних точек

        S.push(XY(D.x,D.y+1,0));

        S.push(XY(D.x-1,D.y,0));

        S.push(XY(D.x,D.y-1,0));

        }

}

Волновой алгоритм. Рекурсивный алгоритм дает нам последовательность выполнения шагов, известную как «рекурсивный обход дерева», которая определяется свойствами стека, его реализующего.

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

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

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

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

• при распространении волны в соседнюю вершину в нее помещается длина пути из начальной: она равна длине пути до текущей (которая уже содержится в текущей вершине согласно этому же алгоритму) плюс расстояние до «соседа»;

• волна распространяется в не пройденные волной вершины;

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

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

//------------------------------------------------------75-02.cpp

// Поиск кратчайших путей на графе – волновой алгоритм

#define N 100

int A[N][N]; // матрица расстояний до соседей

int W[N]; // матрица расстояний от начального

void main(){

int nc=0,ncmp=0;

for (int i=0;i<N;i++) W[i]=-1;

create(0.05);

int n0=0; // Начальная вершина и расстояние до самой себя =0

W[n0]=0;

queue<int,100> Q; // Очередь номеров вершин

Q.in(n0); // Поместить исходную в очередь

while(Q.size()!=0){ // Пока очередь не пуста

        int ni=Q.out();                            // Извлечь номер очередной вершины

        if (W[ni]==-1) continue;               // ошибка - она еще не пройдена

        nc++;                                        // подсчет трудоемкости алгоритма

        for (i=0;i<N;i++)                         // проверка всех соседей

        if (A[ni][i]!=0){                             // Это неотмеченный сосед

                    if (W[i]==-1 || W[i]>W[ni]+A[ni][i])

                                {                       //или сосед с более длинным путем

                                W[i]=W[ni]+A[ni][i]; // Уменьшить длину пути до него

                                Q.in(i);              // Поместить в очередь (вторая волна)

                                }

                    ncmp++;                       // подсчет трудоемкости алгоритма

                    }

        }

for (i=0;i<N;i++) printf("%d ",W[i]);

printf("\nnc=%d ncmp=%d\n",nc,ncmp); }