CODEWITHSUNDEEP
javarecursioncounting
DigitalMan
DigitalMan

Reputation: 41

counting special characters with recursion

I'm trying to code this one up,but I don't get an expected result: 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

Here is my method:

public int countX(String str) {
    int count = 0;

    if(str.length() >= 1 ) {
        if(str.substring(0, 1).equals("x")) {
            str = str.substring(1, str.length());
            count = count + 1 + countX(str);
        }
    }
    else {
        str = str.substring(1, str.length());
        count = count + countX(str);
    }

    return count;
}

Upvotes: 1

Views: 1597

Answers (6)

Morriss
Morriss

Reputation: 31

you can try this one:

public int countX(String str) {
   int end = str.length(); //get length of the string
   int counter = 0;
   if(str.length()==0){
      return counter; //recursion will stop here
   }else{
      if(str.charAt(end-1) == 'x'){
         counter++;
      }
      end--; 
      str=str.substring(0,end); //your string will perform a decrease in length and the last char will be removed
   }
   return counter+countX(str);
}

Upvotes: 0

Adam Evans
Adam Evans

Reputation: 2097

Suppose you have a string "axbxcx". The code below looks only at the first character in the string and determines if it is an x. If so, then return 1 in addition to the number of x's found in the rest of the string. If the first character is not an x, then the number of x's in the string is equal to the number of x's in the string not including the first character, so that is what is returned.

int count(String s)
{
    if (s.length() == 0)   // base case
    {
        return 0;
    }

    if (s.charAt(0) == 'x')
    {
        return 1 + count(s.substring(1));
    }
    else
    {
        return count(s.substring(1));
    }
}

Upvotes: 1

khelwood
khelwood

Reputation: 59185

Here is a simple way to do it.

First, check if the string is empty. This is the terminating condition of the recursion.

Then your result is simply the count for the first character (1 or 0), added to the count for the rest of the string (calculated by calling your function on substring(1)).

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

Upvotes: 0

iullianr
iullianr

Reputation: 1294

You should try this (it assumes you are testing outside the method that initial str value is not null and has a length greater than 0).

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

   }

Upvotes: 0

Andrei
Andrei

Reputation: 7617

How about this?

public static int countX(String str) {

    if (str.length() == 0) {
        return 0;

    } 

    if (str.substring(0, 1).equals("x")) {
        return 1 + countX(str.substring(1));
    }        

    return countX(str.substring(1));
}

Upvotes: 0

Mureinik
Mureinik

Reputation: 311998

You had the right idea, but I think you over complicated things. Just check explicitly if the first character is x (as you have), and only increment count in that case. Regardless of whether it was or wasn't, continue recursing on:

public static int countX(String str) {
    int count = 0;

    if (str.length() > 0) {
        if (str.substring(0, 1).equals("x")) {
            ++count;
        }

        str = str.substring(1, str.length());
        count += countX(str);

    }

    return count;
}

Upvotes: 1

Related Questions