(Java) Trouble with creating a substring in a recursive method

Question

I'm working through Exercise 18.10 the 10th edition of Introduction to Java Programming (Comprehensive Version), which reads as follows:

Write a recursive method that finds the number of occurrences of a specified letter in a string using the following method header:

public static int count(String str, char a)

So here's my implementation of the method:

public static int count(String str, char a)
{

    if (str.charAt(str.length() - 1) != a)
        return 0;
    else
        return 1 + count(str.substring(0, str.length()), a);
}

My base case checks whether the last character is the specified "recurring character"; if it isn't, it adds 1 to a "count" of times the character occurs in the string and recursively invokes the count method.

Running the program with this implementation in place results in a StackOverflowError. I'm guessing this is probably due to infinite recursion, and that it's this bit of code that's causing the problem:

str.substring(0, str.length())

Trouble is, I'm not totally sure I understand why. The description of the substring(int beginIndex, int endIndex) method reads

Returns a string that is a substring of this string. The substring begins at the specified beginIndex and extends to the character at index endIndex - 1.

So the way I have it written, it should return a substring that contains every character in the original string except the last character, thus removing one character of the string at a time through recursion.

I can see why there might be a problem with this in the sense that there's nothing to tell the recursion to stop when the string's length is 1 or 0, but since the problem is a StackOverflowError and not an IndexOutOfBounds exception, I'm a bit lost..

Kh.Taheri · Accepted Answer · 2017-02-02T02:28:46.960

You should call the method (recursively) with the [string - the_last_character], because the last character has been already checked and counted.

Moreover, you have to check whether the string is empty to stop the recursion.

Try this:

public static int count(String str, char a)
{

  if(str.length() == 0) // here we have to stop the recursion as the string is empty!
      return 0;
  if (str.charAt(str.length() - 1) != a)
      return count(str.substring(0, str.length() - 1), a); // here we send the string - the last character which has been already checked.
  else
      return 1 + count(str.substring(0, str.length() - 1), a);
}

score 1 · Answer 2 · answered Feb 02 '17 at 02:01

1

return 1 + count(str.substring(0, str.length()), a)

Herein lies the issue. You're making a recursive call using the whole string. So the function keeps repeating over and over, checking the same character. Instead, return a substring:

return 1 + count(str.substring(0, str.length() - 1), a)

You will also need to add base case for when str.length() == 0.

answered Feb 02 '17 at 02:01

Andrew Jenkins

1,590
13
16

Relevant docs: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring(int,%20int) – nonameable Feb 02 '17 at 02:03

score 0 · Answer 3 · answered Feb 02 '17 at 02:03

The method str.length() doesn't return the index of the last character in the string; it returns the length of the string. Consider the string "A" - the index of the last character is 0 (zero), but str.length() returns 1.

So currently str.substring(0, str.length()) returns a string that is equal to the whole string str.

Instead you want to change your code so that the second argument to substring becomes one character less than the length of the string, so that the result will be one character shorter than the original:

return 1 + count(str.substring(0, str.length() - 1), a);

(Java) Trouble with creating a substring in a recursive method

3 Answers3