재귀 선형 검색 - StackOverflowError

Question

누구든지 올바른 방향으로이 점을 지적 할 수 있는지 알고 싶었습니다. 매우 간단한 것을 간과하는 것처럼 느껴졌습니다. 주된 기능은 약 45,000 단어의 목록에서 검색 방법을 호출하는 것입니다. 나는 문제라고 믿고, 내 코드는 목록의 처음 6 ~ 5 천 단어에있는 단어에 대해 작동하지만 그 후에는 StackOverflow 오류가 발생하고 충돌합니다. 이 작품의 비 재귀 버전은 정상적으로 작동합니다.

나는 배열의 끝인 두 개의 기본 경우를 가지며,이 경우 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

주요 약의 목록에서 검색 메소드를 호출된다 45,000 단어, 나는 문제라고 믿는다.

예, 단어 목록의 큰 길이
은 스택 오버플로를 일으키는 중입니다.
이것은 많은 단어에서 일반적입니다.

Answer 2

스택 오버플로를 반복해서 실행하는 이유는 O (n) 번을 재귀한다는 것입니다. 여기서 n은 목록의 크기입니다. 즉, 목록의 모든 요소에 대해 결과를 찾을 때까지 보존해야하는 함수 스택을 프로그램 스택에 할당합니다. 이렇게하면 자연스럽게 검색 할 수있는 목록의 크기가 제한됩니다.

큰 목록의 경우보다 효율적인 재귀 솔루션 (예 : binary search)이 필요합니다.