如何避免递归堆栈溢出？

-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

如何避免递归堆栈溢出？

回答

相关问题