Как преобразовать рекурсивную функцию в стек?

Question

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

algorithm search(NODE):
  doSomethingWith(NODE)
  for each node CHILD connected to NODE:
    search(CHILD)

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

Как эта функция может быть реализована без рекурсии, а с помощью стека? Во многих случаях много локальных переменных ; где они могут храниться?

Answer 1

Вы измените это, чтобы использовать стек следующим образом:

algorithm search(NODE):
  createStack()
  addNodeToStack(NODE)

  while(stackHasElements)
      NODE = popNodeFromStack()
      doSomethingWith(NODE)
      for each node CHILD connected to NODE:
         addNodeToStack(CHILD)

Что касается вашего второго вопроса:

Во многих случаях существует много локальных переменных;где они могут храниться?

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

Answer 2

Для немного другого обхода.

push(root)
while not empty:
    node = pop
    doSomethingWith node
    for each node CHILD connected to NODE:
        push(CHILD)

Для идентичного обхода подтолкните узлы в обратном порядке.

Если вы раздаете свой стек, это, вероятно, не поможет, так каквместо этого вы взорвете свою кучу

Вы можете избежать толкания всех детей, если у вас есть функция nextChild

Answer 3

Эрик Липперт создал несколько постов на эту тему. Например, взгляните на это: Рекурсия, часть вторая: развертывание рекурсивной функции с явным стеком

Answer 4

По сути, вы обновляете свой собственный стек: char a[] = new char[1024]; или, для безопасности типов, node* in_process[] = new node*[1024]; и помещаете свои промежуточные значения в это:

node** current = &in_process[0];
node* root = getRoot();

recurse( root, &current) ;**

void recurse( node* root, node** current ) ;
  *(*current)++ = root; add a node
  for( child in root ) {
    recurse( child, current );
  }
  --*current; // decrement pointer, popping stack;
}