Text Twist game using recursion

Question

I'm writing a Text Twist game using recursion in C++. For starts, I have a Trie class (contains a TrieNode class) ready for use. My program first loads words from a dictionary and stores them in a Trie object. Then it will prompt the user to enter a 7-letter word. After reading all the letters, I need to use recursion to find all possible combinations of the letters which are words in the loaded dictionary (Trie). These possible words are then stored in another Trie and printed out later. Each possible word have to be at least 3 letters long and must be in the dictionary.

I got stuck at where I need to write a recursion function to search for words, because somehow I don't see how recursion can be applied in this situation. Could someone give me a hint? I don't need comprehensive codes; I just need someone to light that little bulb for me so I'll know where to start. Thanks a lot!

P.S. I also did research on backtracking and the 8-Queen problem but still I'm confused...

This is my main program:

void findWord(int i, const string &word, const Trie&lexion){
    //My question is, what should the base case be?
    //I'm a bit clueless: if I start with this:
    //if(word.length()<=1){
    //      return true;
    //  }
    //  else{
    //      return findWord(i,word.substr(1,word.length()),lexion);
    //  }
    //I know this doesn't make sense; but I'm really lost and don't know where to start.
}

void main(){

    string word;

    Trie lexion = Trie();
    lexion.loadFromFile("ospd.txt");
    word = getWord();//get word from the user

    for (size_t i = 3; i <= 7; i++){
        findWord(i,word,lexion);
    }

}

Answer 1

Basically you want to split the problem into "Can I make a word starting with this letter?" and then recursively descend the Trie to solve for "If I start with this letter can I make a word starting at this node using a subset of the rest of these letters?", and then converting the result from that into a result for the bigger problem, "What words can I make from this string starting at the root of this trie?"

Your recursive function should take in a list (or vector) of letters and a reference to a TrieNode, and should return a list of possible words that exist using that TrieNode as the root.

The termination condition is reaching a leaf node, wherein you return a list with a single empty string, which indicates you found a word. The recursive part is iterating through all the remaining letters in a word, and seeing if any of those can possible be part of a word, and recursively checking each of those (sorry, this is really hard to word correctly..)

Some psuedocode:

list recursiveFind(list input, node curNode)
    if curNode has no children
        // we found a word!
        return list containing ("") (so the caller knows we found a result instead of failing)
    else
        results = empty list
        foreach letter in list
            if find a node where value == letter 
            recursive_results = recursiveFind(input except for that letter, that node you just found)
            foreach result in recursive_results
                push (letter + result) into results
         return results

I hope this helps!