Sortant correctement des récursions?

Question

TrieNode et Trie Objet:

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

     } 
    } 



}; 

Le problème est cette fonction:

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

    } 
} 

Le but est de retourner tous les mots avec le même préfixe d'un DFS en utilisant Trie. Je parviens à récupérer toutes les chaînes nécessaires mais je ne peux pas sortir de la récursivité.

Le code termine la dernière itération de l'instruction if et des interruptions. Visual Studio ne renvoie aucun code d'erreur.

Answer 1

La fin typique d'une récursion est exactement comme vous l'avez dit: return tous les mots. Une norme récursion ressemble à ceci:

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

La question se pose que votre fonction récursive ne peut jamais Retour- il peut soit exécuter le push_back, ou il peut se rappeler. Aucun d'entre eux ne semble sortir correctement, donc il finira soit tranquillement (avec un retour inféré de rien), soit il restera récursif. Dans votre situation, vous devez probablement stocker les résultats de la récursivité dans une structure intermédiaire comme une liste ou une autre, puis renvoyer cette liste après l'itération (puisqu'il s'agit d'une recherche arborescente et doit vérifier tous les enfants, ne pas retourner le premier seulement)

---

Sur cette note, vous semblez manquer une partie du point de recursions- existent pour remplir un but: décomposer un problème en morceaux jusqu'à ce que ces morceaux sont insignifiants à résoudre. Retournez ensuite ce cas et retournez à une solution complète. Toute recherche d'arborescence doit provenir de cette structure de base, ou vous risquez de manquer quelque chose, comme si vous oubliez de return vos résultats.

Answer 2

Vérifiez l'intégrité de votre structure Trie. La fonction semble être correcte. La raison pour laquelle il ne se terminerait pas est si un ou plusieurs de vos nœuds feuilles n'ont pas curr-> nodeChar == NULL.

Un autre cas est que n'importe quel noeud (feuille ou non-feuille) a un noeud enfant garbage. Cela entraînera la récursion à entrer dans la lecture des valeurs inutiles et aucune raison d'arrêter. L'exécution en mode débogage devrait interrompre l'exécution avec un défaut de segmentation. Ecrivez une autre fonction pour tester si tous les nœuds feuille ont une terminaison NULL.

---

EDIT:

Après avoir affiché le code, l'affiche originale a déjà souligné que le problème était qu'il/elle ne retourne pas la liste des chaînes.

En dehors de cela, il y a quelques suggestions que je voudrais fournir à partir du code:

Comment cette boucle while fin si toInsert chaîne est déjà dans la Trie. Vous allez surcharger la chaîne toInsert et lire un caractère poubelle. Il va sortir après cela, mais lire au-delà de votre chaîne est un mauvais moyen de programmer.

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

Cela peut être écrit comme suit:

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

En outre,

Trie(vector<string> dictionary) 

devrait être

Trie(const vector<string>& dictionary) 

car le dictionnaire peut être un grand objet. Si vous ne passez pas par référence, il va créer une deuxième copie. Ce n'est pas efficace.

Answer 3

Je suis un idiot. J'ai oublié de retourner la liste sur la première fonction 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 

}