正確退出遞歸嗎？

Question

TrieNode和特里對象：

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特里樹返回所有單詞。我設法檢索所有必要的字符串，但我不能退出遞歸。

該代碼完成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; 
} 

的問題出現在你的遞歸函數不能return-它可以執行push_back，也可以再次調用本身。這些似乎都不能正常退出，所以它會安靜地結束（推斷什麼也沒有返回），否則它會繼續遞歸。

在你的情況下，你可能需要將遞歸結果存儲在一個像列表或類似的中間結構中，然後在迭代後返回該列表（因爲它是樹搜索並且應該檢查所有的孩子，而不是返回只有第一個）

---

關於這一點，你似乎缺少recursions-點的一部分，它們的存在，以填補一個目的：打破問題成片，直到這些作品是微不足道的解決。然後返回該案例並回到完整的解決方案。任何樹木搜索都必須來自這個基礎結構，否則你可能會錯過某些東西，比如忘記return你的結果。

Answer 2

檢查您的Trie結構的完整性。該功能似乎是正確的。它不會終止的原因是如果一個或多個葉節點沒有curr-> nodeChar == NULL。

另一種情況是任何節點（葉或非葉）都有一個垃圾子節點。這將導致遞歸突破讀垃圾值，沒有理由停止。在調試模式下運行應該通過分段錯誤來中斷執行。

編寫另一個函數來測試所有葉節點是否具有NULL終止。

---

編輯：

發佈代碼後，原來的海報已經指出，問題是，他/她沒有返回字符串列表。

除此之外，還有幾個建議，我想提供基於代碼：

請問這個while循環終止，如果toInsert串已經在特里。 您將溢出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

我是個白癡。我忘記了第一個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 

}