遞歸函數堆棧溢出

該函數採用包含'*'和'？'的字符串wild通配符，並用nodeT *w替換來自樹型數據庫的可能字符的通配符。 out保存一個臨時字符串。每個候選人都被添加到引用的bst。遞歸函數堆棧溢出

void Lexicon::matchRegExpHelper(nodeT *w, string wild, Set<string> &matchSet, string out) 
{ 
    if (wild == "") matchSet.add(out); 

    else { 
     if (wild[0] != '*' || wild[0] != '?') { //this parses up to the wildcard, earlier versions used a position parameter and looped through the prefix chars recursively 
      for (int j = 0; j < w->alpha.size(); j++) 
       if (wild[0] == w->alpha[j].letter) matchRegExpHelper(w->alpha[j].next, wild.substr(1), matchSet, out+=wild[0]); 
     } else { 
      for (int i = 0; i < w->alpha.size(); i++) { 
       if (wild[0] == '?') matchRegExpHelper(w->alpha[i].next, wild.substr(1), matchSet, out+=w->alpha[i].letter);//follow path 
       else { //logically, wild[0] == '*' must be true 
        if (ontLength == (wild.length() + out.length())) matchRegExpHelper(w->alpha[i].next, wild.substr(1), matchSet, out+=w->alpha[i].letter); //ontology is full, treat like a '?' 
        else matchRegExpHelper(w->alpha[i].next, wild.substr(1), matchSet, out+=(w->alpha[i].letter+'*')); //keep adding chars 
       } 
      } 
     } 
    } 
}

當達到第一個通配符功能重新開始 - 我曾試圖與for循環改寫這一點，沒有循環，並在不同的「修剪」的做法。我缺少一些基本的東西，並懷疑這是一個回溯問題。最終堆棧溢出。

問題：1）我在概念上缺少什麼，2）我該如何解決這個功能？

版本沒有for循環 - 測試用例是有點不同，但相似的，我不得不測試它找了一遍

else { 
      if (wild[0] == '?'){ 
       matchRegExpHelper(w, wild, ++pos, matchSet, out);//return and check next path 
       matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=w->alpha[pos].letter);//follow path 
      } 
      if (wild[0] == '*'){ 
       matchRegExpHelper(w, wild, ++pos, matchSet, out);//return and check next path 
       if (ontLength == (wild.length() + out.length()))matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=w->alpha[pos].letter); //ontology is full, treat like a '?' 
       else matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=(w->alpha[pos].letter+'*')); //keep adding chars 
      } 
      if (wild[0] == w->alpha[pos].letter) matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=wild[0]); 

      matchRegExpHelper(w, wild, ++pos, matchSet, out);//check next path 
     } 
     for (int i = 0; i < w->alpha.size(); i++) matchRegExpHelper(w->alpha[i].next, wild.substr(1), 0, matchSet, out+=wild[0]);//step over char

的在端部線圈是固定的溢出企圖，我想也許沒有一些線程的情況下，但我希望那些修剪，所以不知道該怎麼辦

來源

2012-07-27 forest.peterson

您是否嘗試過使用調試器？ – 2012-07-27 10:44:59

@Basile_Starynkevitch也許我不知道dubugger是什麼，但我按下了'開始調試'的綠色箭頭 - 所以我認爲答案是肯定的。 – 2012-07-27 10:53:17

您需要了解如何使用開發工具進行調試。花時間閱讀一些文檔不會有害。您需要放置斷點並查看回溯。 – 2012-07-27 10:54:52

有三個問題與此代碼：

@Basile_Starynkevitch注意使用調試器要採取的路徑的重要性 - 在這種情況下使用VS2008，堆棧允許解析的步驟和注意路徑回到幾個功能。

@Picarus正確地指出在所述終止條件的錯誤

這些解決方案導致發現：

該溶液中，該空隙函數需要兩個return;，一個終止條件之後終止與另一末抓到修剪的線程。從閱讀幾個網站來看，似乎一個無效函數中的return;是不尋常的，但是這種情況下需要遞歸和多重路徑。

來源

2012-07-27 19:18:03

每個遞歸應該有一個基地終止條件。

我的感覺是，

if (wild[0] != '*' || wild[0] != '?')

是錯誤的（即測試始終是真實的，因爲一個字符不能在同一時間'*'和'?'），它應該是一個結合&&不析取||

但正如我在評論說，你真的應該學會如何使用debugger（即把breakpoints，要求backtraces，查詢VALU e變量）。

對調試的熟悉是一種技能，除了這個特定的程序（或作業）之外，對你的整個生活都很有價值。

來源

2012-07-27 11:04:17

這不是家庭作業 - 畢業生，也許就像Dr Evils家庭作業一樣;除非我是教授，那麼也許這是家庭作業 - 實際上汽車旅館現在正在工作:) – 2012-07-27 11:27:18

@Basile_Starynkevitch，我正在重讀您的意見，我看不到您所做的解決方案？另外，我並不是故意聲稱我只想完成這項任務並繼續前進，當然，生命知識是有價值的，我們都將在我們的生活中編寫軟件，我不打算給你留下似乎有的印象已接。 – 2012-07-27 12:33:58

這個條件總是正確的：（！ '？' 野[0] = '*' ||野生[0] =）

由於任何字符是從兩個不同的一個，也許你意味着（野生[0]！= '*' & &野生[0]！= '？'）

我希望這可以幫助你取得一些進展...

而且在概念上，我通常會穿上」 t在遞歸函數中使用'for'，嘗試在不使用'for'的情況下重寫它，可能它會更清晰，可能效率不高，但一旦它起作用，您就可以開始微調該算法..

來源

2012-07-27 11:05:05 Picarus

奇怪，它看起來像和/或邏輯，但你是正確的。有沒有理由避免遞歸循環，我有一個我之前寫的版本，不使用for循環 - 它也有邏輯錯誤。 – 2012-07-27 11:22:20

它仍然溢出，這些都很好，但他們沒有解決這個問題 - 我認爲這是一個回溯問題或從不終止鬆散循環的函數的結果。當我拿到CS和TA解釋它時，我回到了這個問題，那是在'09，雖然 – 2012-07-27 11:25:02

遞歸函數的想法是，它們的工作原理是因爲每次迭代（新調用）解決了一個問題，下一個需要這個作爲先決條件或後置條件，取決於遞歸的種類。 – Picarus 2012-07-31 21:23:51

遞歸函數堆棧溢出

回答

相關問題