CODEWITHSUNDEEP
javarecursion
Javask
Javask

Reputation: 123

Number of 'x' chars in a string - Recursion

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.

Upvotes: 4

Views: 1509

Answers (5)

Mad Physicist
Mad Physicist

Reputation: 114230

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().

Upvotes: 6

dev8080
dev8080

Reputation: 4020

Try this:

public int countX(String str) {
  if (str == null)
    return 0;
  else {
        int occurrence = str.lastIndexOf("x");
        int count = occurrence > -1 ? 1 + countX(str.substring(0, occurrence)) : 0;

        return count;
  }
}

Upvotes: 1

user7605325
user7605325

Reputation:

The else if (str.length() == 1) is not necessary as this condition is already been handled by the return (str.charAt(...

I don't think it can be improved more than that. Actually, I think the problem is too simple to use recursion (using a loop would be pretty much simpler, but as you can't use it...) and the code would be more complicated than needed anyway.

Upvotes: 0

Suresh Atta
Suresh Atta

Reputation: 121998

This looks more clear ?

public static int countX(String str) {
        if (str.length() == 0) {
            return 0;
        }
        int count = 0;
        if (str.charAt(0) == 'x') {
            count++;
        }
        return count + countX(str.substring(1));
    }

Upvotes: 1

Mureinik
Mureinik

Reputation: 311143

The special treatment for a string of length 1 is redundant - it's already covered by the else clause:

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

Upvotes: 1

Related Questions