java递归线性搜索堆栈溢出错误

Question

我想看看是否有人能给我指出正确的方向，我觉得我忽略了一些非常简单的事情，主要是在一个大约45000个单词的列表中调用搜索方法，我认为这是问题所在，我的代码适用于列表中前6000个单词中的单词，但在那之后，它遇到了堆栈溢出错误并崩溃。我有一个非递归的版本，效果很好

我有两个基本情况，它们是数组的结尾，在这种情况下我们抛出ItemNotFoundException，如果找到了这个词，在这种情况下我们返回该项所在的索引

我目前的代码是：

public int search(String[] words, String wordToFind)
            throws ItemNotFoundException {
        return search(words, wordToFind, 0);
    }

    private int search(String[] words, String wordToFind, int index) {
        incrementCount();
        if(index == words.length) {
            // If index gets to the end of the array, then the word is not in the array
            throw new ItemNotFoundException();
        }
        if (words[index].equals(wordToFind)) {
            // If word is found, return the index.
            return index;
        } else {
            // Increment index by 1
            index++;
            // Call the search again
            return search(words, wordToFind, index);
        }
    }

工作正常的非递归代码：

    public int search(String[] words, String wordToFind)
        throws ItemNotFoundException {
    int count = 0;
    for (String word : words) {
        incrementCount();
        if (word.equals(wordToFind)) {
            return count;
        }
        count++;
    }
    throw new ItemNotFoundException();

}

Answer 1

这个很好用！递归地

static int search(String[] words, String wordToFind, int index){
     if (index >= words.length)
         return -1;
     if (words[index] == wordToFind)
         return index;
     return search(words, wordToFind, index+1);
}

public static void main(String[] args) {
    String[] words = {"one", "tw0", "hello", "world"};
    String wordToFind = "hello";
    System.out.println("Index of "+ wordToFind+" in words => "+ search(words,wordToFind,0));
}

Answer 2

the main is calling the search method on a list of about 45,000 words, which I believe is the problem

是的，单词列表非常长
正在导致堆栈溢出
这对这么多单词来说是正常的