Number of 'x' chars in a string - Recursion

Question

I'm practicing pretty basic recursion problems in Java.

"Given a string, compute recursively (no loops) the number of lowercase 'x' chars in the string"

countX("xxhixx") → 4

countX("xhixhix") → 3

countX("hi") → 0

-

 public int countX(String str) {
      if (str == null || str.length() == 0)
        return 0;
      else if (str.length() == 1)
        return str.charAt(0) == 'x' ? 1 :0;
      else {
        return (str.charAt(str.length()-1) == 'x' ? 1 : 0 ) + countX(str.substring(0,str.length()-1));
      }
    }

This works fine. But, I would like to know if there is any better way of writing it. I find this code complex for a simple problem.

Answer 1

The main reason you think this is cumbersome is that it is. A recursive solution is just generally not optimal for counting things in a string or array. Besides the fact that the code looks strange, at least to me, you are actually creating a new stack frame and a new version of the string for every character. This is inefficient (although I wonder if String.substring is optimized to point to the original buffer instead of making a full copy, given that strings are immutable).

However, given the constraints of your problem, you could probably get rid of a few redundant checks that you do in your code:

public int countX(String str) {
    if(str == null || str.isEmpty())
        return 0;
    return (str.charAt(0) == 'x' ? 1 : 0) + countX(str.substring(1));

Since you already test for null and empty strings, a string of length 1 is no longer a special case.

By removing the first character at each iteration instead of the last, you make the indexing and the call to substring much cleaner. This also removes two explicit calls to str.length().