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

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

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

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

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

Ответ 1

Вы меняете это так, чтобы использовать такой стек:

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

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 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;
}