title: Recursive Linear Search - StackOverflowError
body: <p>I wanted to see if anyone could point me in the right direction on this, I feel like I am overlooking something very simple, the main is calling the search method on a list of about 45,000 words, which I believe is the problem, my code works for words that are in the first 6 or so thousand words in the list, but after that it encounters a StackOverflow error and crashes. I have a version of this that is non-recursive that works fine. </p>
  
  <p>I have two base cases, which are the end of the array, in which case we throw ItemNotFoundException, and if the word is found, in which case we return the index at which the item was located. </p>
  
  <p>My current code is: </p>
  
  <pre><code>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);
          }
      }
  </code></pre>
  
  <p>Non-recursive code that works fine: </p>
  
  <pre><code>    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();
  </code></pre>
  
  <p>}</p>