c++ - 正确退出递归？

Question

TrieNode 和 Trie 对象:

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

        }
    }



};

问题是这个函数:

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

    }
}

目的是使用 DFS 从 trie 中返回所有具有相同前缀的词。我设法检索了所有必要的字符串，但我无法退出递归。

代码完成 if 语句的最后一次迭代并中断。 Visual Studio 不会返回任何错误代码。

Answer 1

递归的典型结束就像你说的那样 - return 所有单词。标准递归看起来像这样:

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

出现问题的原因是您的递归函数永远无法返回 - 它可以执行 push_back，也可以再次调用自身。这些似乎都没有正确退出，所以它要么安静地结束(推断没有返回)，要么继续递归。

在您的情况下，您可能需要将递归的结果存储在中间结构(如列表等)中，然后在迭代后返回该列表(因为它是树搜索并且应该检查所有子项，而不是返回只有第一个)

---

关于这一点，您似乎遗漏了递归的一部分 - 它们的存在是为了满足一个目的:将问题分解成多个部分，直到这些部分变得微不足道。然后返回该案例并重新构建完整的解决方案。任何树搜索都必须来自这个基本结构，否则您可能会遗漏一些东西 - 比如忘记返回您的结果。