Why is my stack-based implementation of this code so much slower than recursion?

I have a tree whose nodes store either -1 or a non-negative integer that is the name of a vertex. Each vertex appears at most once within the tree. The following function is a bottleneck in my code:

Version A:

void node_vertex_members(node *A, vector<int> *vertexList){
   if(A->contents != -1){
      vertexList->push_back(A->contents);
   }
   else{
      for(int i=0;i<A->children.size();i++){
          node_vertex_members(A->children[i],vertexList);
      }
   }
}

Version B:

void node_vertex_members(node *A, vector<int> *vertexList){
   stack<node*> q;
   q.push(A);
   while(!q.empty()){
      int x = q.top()->contents;
      if(x != -1){
         vertexList->push_back(x);
         q.pop();
      }
      else{
         node *temp = q.top();
         q.pop();
         for(int i=temp->children.size()-1; i>=0; --i){
            q.push(temp->children[i]);
         }
      }
   }
}

For some reason, version B takes significantly longer to run than version A, which I did not expect. What might the compiler be doing that's so much more clever than my code? Put another way, what am I doing that's so inefficient? Also perplexing to me is that if I try anything such as checking in version B whether the children's contents are -1 before putting them on the stack, it slows down dramatically (almost 3x). For reference, I am using g++ in Cygwin with the -O3 option.

Update:

I was able to match the recursive version using the following code (version C):

node *node_list[65536];

void node_vertex_members(node *A, vector<int> *vertex_list){
   int top = 0;
   node_list[top] = A;
   while(top >= 0){
      int x = node_list[top]->contents;
      if(x != -1){
         vertex_list->push_back(x);
         --top;
      }
      else{
         node* temp = node_list[top];
         --top;
         for(i