Правильно выходя из рекурсий?

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. Мне удается получить все необходимые строки, но я не могу выйти из рекурсии.

Код завершает последнюю итерацию оператора 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, или он может называть себя снова. Ни один из них, похоже, не подходит, поэтому он либо закончится тихо (с предполагаемым возвратом ничего), либо продолжит рекурсию.

В вашей ситуации вам, скорее всего, нужно будет сохранить результаты рекурсии в промежуточной структуре, подобной списку или тому подобному, а затем вернуть этот список после итерации (поскольку это поиск по дереву и должен проверять всех детей, а не возвращать только первые один)

---

на этой ноте, вы, кажется, отсутствуют часть точки recursions- они существуют, чтобы заполнить цель: разбить задачу на часть, пока эти части не тривиальны решить. Затем верните этот случай и вернитесь к полному решению. Любой поиск по дереву должен происходить из этой базовой структуры, или вы можете пропустить что-то вроде забывания до return ваших результатов.

Answer 2

Проверьте целостность структуры Trie. Функция выглядит правильно. Причина, по которой он не прекращается, заключается в том, что если один или несколько ваших листовых узлов не имеют curr-> nodeChar == NULL.

Другое дело, что любой узел (листовой или нелистный) имеет дочерний узел мусора. Это приведет к перерыву рекурсии в считывание значений мусора и никаких оснований для остановки. Запуск в режиме отладки должен прервать выполнение с ошибкой сегментации.

Напишите еще одну функцию, чтобы проверить, есть ли у всех листовых узлов NULL-окончание.

---

EDIT:

После размещения кода, оригинальный плакат уже указал, что проблема заключалась в том, что он/она не возвращает список строк.

Кроме того, есть несколько предложений, я хотел бы представить на основе кода:

Как это в то время как цикл прекращается, если toInsert строка уже в TRIE. Вы набегаете строку 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 

}