How to convert a recursive function to use a stack?

Question

Suppose that I have a tree to traverse using a Depth First Search, and that my algorithm for traversing it looks something like this:

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

Now in many languages there is a maximum depth to recursion, for example if the depth of recursion is over a certain limit, then the procedure will crash with a stack overflow.

How can this function be implemented without the recursion, and instead with a stack? In many cases, there are a lot of local variables; where can they be stored?

Answer 1

Essentially you new up your own stack: char a[] = new char[1024]; or for type-safety, node* in_process[] = new node*[1024]; and put your intermediate values on this:

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;
}

Answer 2

For a slightly different traversal.

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

For an identical traversal push the nodes in reverse order.

If you are blowing your stack, this probably won't help, as you'll blow your heap instead

You can avoid pushing all the children if you have a nextChild function

Answer 3

You change this to use a stack like so:

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

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

As for your second question:

In many cases, there are a lot of local variables; where can they be stored?

These really can be kept in the same location as they were originally. If the variables are local to the "doSomethingWith" method, just move them into that, and refactor that into a separate method. The method doesn't need to handle the traversal, only the processing, and can have it's own local variables this way that work in its scope only.

Answer 4

Eric Lippert has created a number of posts about this subject. For example take a look at this one: Recursion, Part Two: Unrolling a Recursive Function With an Explicit Stack