Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Count Letter recursive method

So the program has to count letters of a string. I am not allowed to use loops except of recursive ones.

The method has to look like this:

static int numberOf(String text, char characterToCount)

Input:

abcbabcba (String) and b (char)

Output:

4

That's what my Code looks like so far ( I get Stackoverflow ) :

static int numberOf(String text, char characterToCount) {
 int i = 0;
 int erg = 0;
 if (text.length() != 0) {
   if (i != text.length()) {
     if (text.charAt(i) == characterToCount) {
       i++;
       erg++;
       numberOf(text, characterToCount);
     } else {
       i++;
       numberOf(text, characterToCount);
     }
   } else {
     return erg;
   }
 }

 return 0;
}

EDIT

I'm only allowed to use String.charAt and String.length

like image 446
daniel.309 Avatar asked Dec 26 '20 01:12

daniel.309


2 Answers

The problem is that you aren't reducing text when you call the method so the length is never reduced to 0. Here is what you should be doing. Note that you do not need to pass an index to the method. Just keep reducing the text by 1 each time and just check the first character for equality to the target character.

public static void main(String[] args) {
    System.out.println(numberOf("ksjssjkksjssss", 's'));
}
    
    
static int numberOf(String text, char characterToCount) {
    if (text.isEmpty()) {
        return 0;
    }
    
    if (text.charAt(0) == characterToCount) {
        // call method and add 1 since you found a character
        return numberOf(text.substring(1), characterToCount) + 1;
    }
    // just call the method.
    return numberOf(text.substring(1), characterToCount);
    
}

The above prints

8

Ok, here is my modified version to meet your requirements of using only String.length and String.charAt. The char is really 16 bits so I use the high order byte to store the current index. I increment that index for each recursive call to maintain the current position of the search. When I add 256 to the character I am really adding 1 to the high order byte.

static int numberOf(String text, char ch) {
    // stop when index exceeds text length
    if (ch >> 8 >= text.length()) {
        return 0;
    }
    if (text.charAt((ch >> 8)) == (ch & 0xff)) {
        return numberOf(text, (char)(ch + 256)) + 1;
    }
    return numberOf(text, (char)(ch + 256));
}

This will not work as written on some character sets that are wider than 8 bits.

like image 86
WJS Avatar answered Nov 19 '22 12:11

WJS


WJS's answer looks good but if you want simpler solution, this might help as well.

The problem in your solution is that your update of i and erg in one call stack is not seen/used by the next recursive call stack, since they are local variables and every stack will have their own copy of i and erg. They are always initialized as 0 in every call of numberOf method.

If substring isn't allowed then one way would be to make use of an extra variable that holds the index of position in the text you are comparing.

But on doing so you'll probably have to modify the signature of your method (if you don't want to use a class level static variable). And since you've mentioned that your method has to have only two arguments (text, charToCount), one way to achieve this easily would be to make use of a helper method (containing extra index argument) and your method can call it.

static int numberOf(String text, char characterToCount) {
    return helper(text, characterToCount, 0);
}

static int helper(String text, char charToCount, int index) {
    if (text.isEmpty() || index == text.length()) return 0;

    int countCharOnRight = helper(text, charToCount, index+1);

    return (text.charAt(index) == charToCount) ? 1 + countCharOnRight : countCharOnRight;
} 
like image 4
user0904 Avatar answered Nov 19 '22 11:11

user0904