如何避免遞歸堆棧溢出？

-1

編輯：只是爲了澄清，遞歸需要爲任務的一部分，所以它必須是遞歸的，即使我知道這不是做這個問題如何避免遞歸堆棧溢出？

最好的方式，我做了一個節目，在部分將搜索一個非常大的字典，並將給定的單詞列表與字典中的每個單詞進行比較，並返回以用戶給定單詞的相同兩個字母開頭的單詞列表。

這適用於小型字典，但我剛剛發現，對於超過一定數量的字典存在遞歸堆棧限制，所以我得到一個堆棧溢出錯誤。

我的想法是將每個遞歸限制爲1000次遞歸，然後爲另一個1000遞增計數器，然後再次從遞歸方法最後離開的位置開始，然後在2000年再次結束，然後重新開始，直到字典結束。

這是最好的方法嗎？如果是這樣，有沒有人有任何想法如何？我很難實現這個想法！

（編輯：如果不是最好的辦法，有沒有人對如何更有效地做到這一點的任何想法）

這裏是我到目前爲止，1000遞歸思想幾乎沒有實現的代碼因爲我已經刪除了我過去試過的一些代碼，但老實說，它和我在這裏所得到的一樣有幫助。

電話：

for(int i = 0; i < givenWords.size(); i++){ 
     int thousand = 1000; 
     Dictionary.prefix(givenWords.get(i), theDictionary, 0, thousand); 
     thousand = thousand + 1000; 
    }

和前綴方法：

public static void prefix (String origWord, List<String> theDictionary, int wordCounter, int thousand){ 

    if(wordCounter < thousand){ 
      // if the words don't match recurse through this same method in order to move on to the next word 
     if (wordCounter < theDictionary.size()){ 
      if (origWord.charAt(0) != theDictionary.get(wordCounter).charAt(0) || origWord.length() != theDictionary.get(wordCounter).length()){ 
       prefix(origWord, theDictionary, wordCounter+1, thousand+1); 

      } 

      // if the words first letter and size match, send the word to prefixLetterChecker to check for the rest of the prefix. 
      else{ 
       prefixLetterChecker(origWord, theDictionary.get(wordCounter), 1); 
       prefix(origWord, theDictionary, wordCounter+1, thousand+1); 
      } 
     } 
    } 
    else return; 
    }

編輯澄清：

的字典是一個有序的大字典，每行只有一個字，小寫字母

t他「給出的單詞」實際上是一個列表中的一個，在該程序中，用戶輸入一個2-10個字符之間的字符串，字母只有空格等等。程序創建一個列表，列出該字符串的所有可能的排列，然後通過這些排列的數組以及每個排列返回以給定單詞的前兩個字母開始的另一個單詞列表。

如果程序正在通過它，任何字母直到前兩個字母都不匹配，程序就會轉到下一個給定的單詞。

來源

2014-10-18 Maribov

遞歸是必需的作爲一項任務的一部分 – Maribov 2014-10-18 01:27:02

啊。在這種情況下，使用[*二進制搜索*]（http://en.wikipedia.org/wiki/Binary_search_algorithm）編寫它。這會減少從'n'到'lg（n）'的深度並避免堆棧溢出。唯一的要求是字典是排序的。由於匹配的字母可以「分割」一個i/2分區，因此您需要考慮退出情況以查找也匹配的第一個/最後一個字。 – user2864740 2014-10-18 01:28:34

嗯好吧我會研究二進制搜索，字典排序 – Maribov 2014-10-18 01:31:18

這實際上是一個很好的任務。讓我們做一些假設....

26個字母在字母表中，所有單詞都在這些字母中。
單個單詞不超過... 1000個字符長。

創建一類，稱之爲 '節點'，看起來像：

private static class Node { 
    Node[] children = new Node[26]; 
    boolean isWord = false; 
}

現在，創建一個使用這個節點類的樹。這棵樹的根是：

private final Node root = new Node();

然後，詞典中的第一個單詞是單詞'a'。我們將它添加到樹中。需要注意的是 '一' 是字母0

所以，我們在給樹 '遞歸'：

private static final int indexOf(char c) { 
    return c - 'a'; 
} 

private final Node getNodeForChars(Node node, char[] chars, int pos) { 
    if (pos == chars.length) { 
     return this; 
    } 
    Node n = children[indexOf(chars[pos])]; 
    if (n == null) { 
     n = new Node(); 
     children[indexOf(chars[pos])] = n; 
    } 
    return getNodeForChars(n, chars, pos + 1); 
}

所以，與這一點，你可以簡單地做：

Node wordNode = getNodeForChars(root, word.toCharArray(), 0); 
wordNode.isWord = true;

所以，您可以創建字樹.....現在，如果你需要找到以字母（在prefix）給定的序列中的所有的話，你可以這樣做：

Node wordNode = getNodeForChars(root, prefix.toCharArray(), 0);

現在，如果isWord爲true，則此節點及其所有非空和isWord爲真的子節點都是帶有前綴的詞。你只需要重建序列。您可能會發現將實際單詞存儲爲Node的一部分而不是布爾isWord標誌是有利的。你的來電。

遞歸深度永遠不會超過最長的單詞。數據密度很大。還有其他方法可以設置節點，可能在性能或空間方面更高效（或更低效）。然而，這個想法是，你在廣泛的樹中設置你的數據，因此你的搜索速度非常快，並且任何點的所有子節點都具有與父節點相同的前綴（或者，父節點是前綴）。

來源

2014-10-18 01:41:39 rolfl

如何避免遞歸堆棧溢出？

回答

相關問題