Как преобразовать рекурсивную функцию для использования стека?
Предположим, что у меня есть дерево для пересечения использования Поиска в глубину, и что мой алгоритм для того, чтобы пересечь его выглядит примерно так:
algorithm search(NODE):
doSomethingWith(NODE)
for each node CHILD connected to NODE:
search(CHILD)
Теперь на многих языках существует максимальная глубина к рекурсии, например, если глубина рекурсии будет по определенному пределу, то процедура откажет с переполнением стека.
Как это может функционировать быть реализованным без рекурсии, и вместо этого со стеком? Во многих случаях существует много локальных переменных; где они могут быть сохранены?
4 ответа
Вы меняете это так, чтобы использовать стек следующим образом:
algorithm search(NODE):
createStack()
addNodeToStack(NODE)
while(stackHasElements)
NODE = popNodeFromStack()
doSomethingWith(NODE)
for each node CHILD connected to NODE:
addNodeToStack(CHILD)
Что касается вашего второго вопроса:
Во многих случаях существует много локальных переменных; где они могут храниться?
Их действительно можно хранить в том же месте, где они были изначально. Если переменные являются локальными по отношению к методу «doSomethingWith», просто переместите их в него и реорганизуйте его в отдельный метод. Этому методу не требуется обрабатывать обход, только обработку, и он может иметь собственные локальные переменные, которые работают только в его области действия.
По сути, вы создаете свой собственный стек: char a[] = new char[1024]; или для безопасности типов, node* in_process[] = new node*[1024]; и помещаете свои промежуточные значения на это:
node** current = &in_process[0];
node* root = getRoot();
recurse( root, ¤t) ;**
void recurse( node* root, node** current ) ;
*(*current)++ = root; add a node
for( child in root ) {
recurse( child, current );
}
--*current; // decrement pointer, popping stack;
}
Эрик Липперт создал несколько сообщений на эту тему. Например, взгляните на это: Рекурсия, часть вторая: развертывание рекурсивной функции с помощью явного стека
Для немного другого обхода.
push(root)
while not empty:
node = pop
doSomethingWith node
for each node CHILD connected to NODE:
push(CHILD)
Для идентичного обхода сдвиньте узлы в обратном порядке.
Если вы взорвете свой стек, это, вероятно, не поможет, так как вместо этого вы взорвете свою кучу
Вы можете избежать выталкивания всех дочерних элементов, если у вас есть функция nextChild