Properly exiting out of recursions?

Question

TrieNode and Trie Object:

struct TrieNode {

    char nodeChar = NULL;
    map<char, TrieNode> children;

    TrieNode() {}
    TrieNode(char c) { nodeChar = c; }
};


struct Trie {
    TrieNode *root = new TrieNode();
    typedef pair<char, TrieNode> letter;
    typedef map<char, TrieNode>::iterator it;

    Trie(vector<string> dictionary) {
        for (int i = 0; i < dictionary.size(); i++) {
            insert(dictionary[i]);
        }
    }

    void insert(string toInsert) {
        TrieNode * curr = root;
        int increment = 0;
        // while letters still exist within the trie traverse through the trie
        while (curr->children.find(toInsert[increment]) != curr->children.end()) { //letter found
            curr = &(curr->children.find(toInsert[increment])->second);
            increment++;
        }
        //when it doesn't exist we know that this will be a new branch 
        for (int i = increment; i < toInsert.length(); i++) {
            TrieNode temp(toInsert[i]);
            curr->children.insert(letter(toInsert[i], temp));
            curr = &(curr->children.find(toInsert[i])->second);
            if (i == toInsert.length() - 1) {
                temp.nodeChar = NULL;
                curr->children.insert(letter(NULL, temp));
            }

        }
    }


    vector<string> findPre(string pre) {
        vector<string> list;
        TrieNode * curr = root;
        /*First find if the pre actually exist*/
        for (int i = 0; i < pre.length(); i++) {
            if (curr->children.find(pre[i]) == curr->children.end()) { //DNE
                return list;
            }
            else {
                curr = &(curr->children.find(pre[i])->second);
            }
        }
        /*Now curr is at the end of the prefix, now we will perform a DFS*/

        pre = pre.substr(0, pre.length() - 1);
        findPre(list, curr, pre);

    }

    void findPre(vector<string> &list, TrieNode *curr, string prefix) {
        if (curr->nodeChar == NULL) {
            list.push_back(prefix);
            return;
        }
        else {
            prefix += curr->nodeChar;
            for (it i = curr->children.begin(); i != curr->children.end(); i++) {
                findPre(list, &i->second, prefix);
            }

        }
    }



};

The problem is this function:

void findPre(vector<string> &list, TrieNode *curr, string prefix) {

/*if children of TrieNode contains NULL char, it means this branch up to this point is a complete word*/
    if (curr->nodeChar == NULL) { 
        list.push_back(prefix);
    }
    else {
        prefix += curr->nodeChar;
        for (it i = curr->children.begin(); i != curr->children.end(); i++) {
            findPre(list, &i->second, prefix);
        }

    }
}

The purpose is to return all words with the same prefix from a trie using DFS. I manage to retrieve all the necessary strings but I can't exit out of the recursion.

The code completes the last iteration of the if statement and breaks. Visual Studio doesn't return any error code.

Answer 1

Check the integrity of your Trie structure. The function appears to be correct. The reason why it wouldn't terminate is if one or more of your leaf nodes doesn't have curr->nodeChar == NULL.

Another case is that any node (leaf or non-leaf) has a garbage child node. This will cause the recursion to break into reading garbage values and no reason to stop. Running in debug mode should break the execution with segmentation fault.

Write another function to test if all leaf-nodes have NULL termination.

---

EDIT:

After posting the code, the original poster has already pointed out that the problem was that he/she was not returning the list of strings.

Apart from that, there are a few more suggestions I would like to provide based on the code:

How does this while loop terminate if toInsert string is already in the Trie. You will overrun the toInsert string and read a garbage character. It will exit after that, but reading beyond your string is a bad way to program.

// while letters still exist within the trie traverse through the trie
while (curr->children.find(toInsert[increment]) != curr->children.end()) 
{ //letter found
    curr = &(curr->children.find(toInsert[increment])->second);
    increment++;
}

This can be written as follows:

while (increment < toInsert.length() && 
curr->children.find(toInsert[increment]) != curr->children.end())

Also,

Trie( vector<string> dictionary)

should be

Trie( const vector<string>& dictionary )

because dictionary can be a large object. If you don't pass by reference, it will create a second copy. This is not efficient.

Answer 2

I am a idiot. I forgot to return list on the first findPre() function.

    vector<string> findPre(string pre) {
    vector<string> list;
    TrieNode * curr = root;
    /*First find if the pre actually exist*/
    for (int i = 0; i < pre.length(); i++) {
        if (curr->children.find(pre[i]) == curr->children.end()) { //DNE
            return list;
        }
        else {
            curr = &(curr->children.find(pre[i])->second);
        }
    }
    /*Now curr is at the end of the prefix, now we will perform a DFS*/

    pre = pre.substr(0, pre.length() - 1);
    findPre(list, curr, pre);
    return list; //<----- this thing

}

Answer 3

The typical end to a recursion is just as you said- return all words. A standard recursion looks something like this:

returnType function(params...){
    //Do stuff
    if(need to recurse){
        return function(next params...);
    }else{ //This should be your defined base-case
        return base-case;
}

The issue arises in that your recursive function can never return- it can either execute the push_back, or it can call itself again. Neither of these seems to properly exit, so it'll either end quietly (with an inferred return of nothing), or it'll keep recursing.

In your situation, you likely need to store the results from recursion in an intermediate structure like a list or such, and then return that list after iteration (since it's a tree search and ought to check all the children, not return the first one only)

---

On that note, you seem to be missing part of the point of recursions- they exist to fill a purpose: break down a problem into pieces until those pieces are trivial to solve. Then return that case and build back to a full solution. Any tree-searching must come from this base structure, or you may miss something- like forgetting to return your results.