Recursion -> Iteration

Question

With the following Trie Struct:

struct Trie{
    char letter;
    bool eow;
    Trie *letters[26];
};

I'm using the following code to extract words from a trie into a vector in alphabetic order.

void getWords(const TrieNode& data, vector<string> &words, string acc)
{
  if (data.eow)
    words.push_back(acc);

  for (int i = 0; i < 26; i++) {
    if (data.letters[i] != NULL)
      getWords(*(data.letters[i]), words, acc + data.letters[i]->letter);
  }
}

I was just wondering if there was a way to do this without recursion, and using only iteration? I'm trying to implement this with only iteration, but can't think of a way to check every letter of each layer in the trie, using loops. Any suggestions?

If the question is really just "is there a way to do it without recursion?" then yes, of course. If you are asking "how do I do it?" then the short answer is to use a stack. — Ray Toal, Oct 27 '12 at 19:53
can you please add the language tag? eg [tag:c] or [tag:c++] — Bohemian, Oct 27 '12 at 19:53
You could at least post a struct definition that has a hope of compiling. — Puppy, Oct 27 '12 at 19:57
See: http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration — , Oct 27 '12 at 19:59

score 0 · Answer 1 · answered Oct 27 '12 at 20:22

struct State {
  const TrieNode* data;
  string acc;
  int index;
  State( ... ): ... {} // element-wise constructor, left as an exercise
};

std::vector<string> getWords( const TrieNode* root )
{
  std::vector<string> retval;
  std::vector<State> states;
  states.push_back( State( root, string(), 0 ) );
  while (!states.empty())
  {
    State s = states.back();
    states.pop_back();
    if (s.data->eow)
    {
      retval.push_back( s.acc );
      continue;
    }
    if (s.index >= 26)
      continue;
    states.push_back( State( s.data, s.acc, s.index+1 ) );
    if (s.letters[s.index])
    {
      states.push_back( State( s.letters[s.index], s.acc + s.letters[s.index]->letter, 0 ) );
    }
  }
  return std::move(retval);
};

The states is an explicit stack that tracks the same data as you tracked recursively, pretty much. I think I managed to visit the elements in the same order your recursive function would, but that wouldn't really matter.

Note that the above code is written and not tested, and you have to write an element-wise constructor for State, because I'm lazy.

Is there a way to do it with like a loop in a loop ? or you suggesting i make a State class/struct — John Smith, Oct 27 '12 at 20:46
I was suggesting you make an explicit stack. You can have less details in the stack, and you could probably even pull off using your acc string as a stack. I would not recommend it. — Yakk - Adam Nevraumont, Oct 27 '12 at 21:34

Recursion -> Iteration

1 Answers1