正确退出递归？

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

    }
}

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

代码完成 if 语句的最后一次迭代并中断。 Visual Studio 没有 return 任何错误代码。

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

问题在于您的递归函数永远无法 return- 它可以执行 push_back，或者可以再次调用自身。这些似乎都没有正确退出，所以它要么安静地结束（推断 return 什么都没有），要么继续递归。

在您的情况下，您可能需要将递归的结果存储在列表等中间结构中，然后在迭代后 return 该列表（因为它是树搜索并且应该检查所有children，不是 return 第一个）

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

Answer 2

检查您的 Trie 结构的完整性。该功能似乎是正确的。它不会终止的原因是如果一个或多个叶节点没有 curr->nodeChar == NULL。

另一种情况是任何节点（叶子或非叶子）都有一个垃圾子节点。这将导致递归中断读取垃圾值并且没有理由停止。运行在调试模式下应该会因分段错误而中断执行。

编写另一个函数来测试是否所有叶节点都以 NULL 终止。

编辑：

贴出代码后，楼主已经指出问题是he/she没有返回字符串列表。

除此之外，我还想根据代码提供一些建议：

如果 toInsert 字符串已经在 Trie 中，这个 while 循环如何终止。您将超出 toInsert 字符串并读取垃圾字符。之后它会退出，但读取超出字符串的范围是一种糟糕的编程方式。

// 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++;
}

可以这样写：

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

此外，

Trie( vector<string> dictionary)

应该是

Trie( const vector<string>& dictionary )

因为字典可以是一个大对象。如果您不通过引用传递，它将创建第二个副本。这效率不高。

Answer 3

我是个白痴。我忘了 return 列出第一个 findPre() 函数。

    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

}

正确退出递归？

Properly exiting out of recursions?

c++

recursion

trie