CODEWITHSUNDEEP
javastringrecursioncountcharacter
Noob
Noob

Reputation: 534

Recursively counting character occurrences in a string

Im making a program to count the number of times a character is found in a string. This is what my method looks like:

public static int count (String line, char c)
{
    int charOccurences = 0; //= 0;

    for (int x = 0 ; x < line.length () ; x++)
    {
        if (line.charAt (x) == c)
        {
            charOccurences++;
            line = line.substring (0, x) + line.substring (x + 1);
            return count (line, c);
        }
        else
            return charOccurences;
    }
    return charOccurences;
}

It always returns 0, due to the fact that once the method calls itself it sets charOccurences back to 0. But i need to declare that variable for the method to work. I cant figure any way around this. Any help would be appreciated.

Upvotes: 4

Views: 17999

Answers (8)

vishwajit dalve
vishwajit dalve

Reputation: 9

Please remove the else loop inside the for loop. If you keep that loop you should get occurrence of only one character.

public static int count (String line, char c)
{
    int charOccurences = 0; //= 0;

    for (int x = 0 ; x < line.length () ; x++)
    {
        if (line.charAt (x) == c)
        {
            charOccurences++;
            line = line.substring (0, x) + line.substring (x + 1);
            return count (line, c);
        }
    }
    return charOccurences;
}

Upvotes: 0

Roland
Roland

Reputation: 208

i had the same issue you can always do this i did it on a word same applies for a sentence

private static int count(String word, String letter) {
    int count = 0;
 return occurrence(word, letter, count);
}

private static int occurrence(String word, String letter, int count) {
if () 
base case 
else 
// compare and increment if it matches..
return occurrence(word.substring(0, word.length() - 1), letter,count)

}

the other method occurrence be the recursion method, and repeat your code now count is already defined and you can increment without having any problem! :)

Upvotes: 0

Vincent Zgueb
Vincent Zgueb

Reputation: 1491

Despite doing it recursively is not required (let's do it for fun). You were almost done. Just be sure to have a condition that stops the recursion: here it is if (len == 0)… statement.

public static int count (String line, char c)
{
    int len = line.length();
    if ((len == 0) || (c == '\0'))   // obvious case for empty string or nil char.
       return 0;                     // Your recursion always ends here

    String rest = line.substring(1);
    if (line.charAt(0) == c)     
    {
       return count(rest, c) + 1;   // recurse on substring
    }
    else
    {
       return count(rest, c);   // recurse on substring
    }
}

Upvotes: 0

SiKing
SiKing

Reputation: 10329

I think you're making it much harder than it needs to be?

public static int count(String line, char c) {
    int orig = line.length();
    int repl = line.replaceAll("" + c, "").length();
    return orig - repl;
}

Upvotes: 0

Rainbolt
Rainbolt

Reputation: 3660

You ignored charOccurences right after you incremented it.

charOccurences++;
line = line.substring (0, x) + line.substring (x + 1);
return charOccurences + count (line, c); // Fixed for you.

Others have mentioned that you don't need a for loop at all. If you wanted to do this purely recursively, you would simply lose the loop, and follow these steps:

  • base case:
    • first character doesn't exist (length is zero)
      • return 0;
  • recursion case:
    • The first character does exist
      • if it matches, increment occurrences
      • else do nothing
      • return (occurrences) + (result of recursing with substring);

Upvotes: 4

ajb
ajb

Reputation: 31689

Here's a general approach for writing recursive methods for tasks that really shouldn't be recursive but have to be because you're learning about recursion in class:

Find a way to break the problem down into a smaller problem(s).

Here, your problem is to count the occurrences of character c in a string. Well, suppose you break your string down into "the first character" and a substring of "all the other characters". You can tell whether the first character equals c. Then you look at "all the other characters", and if that's not empty (the base case), then that's just a smaller version of the same problem. So you can use recursion on that. So pretend the recursion already happened, so then you know: (1) is the first character equal to c, and (2) how many occurrences of c are there in the smaller string. Once you know those two pieces of data, you should be able to figure out how many occurrences of c there are in the whole string.

For this problem, your solution should not have a loop in it.

Upvotes: 2

libik
libik

Reputation: 23029

Yea, it is very easy to do it recursively :)

public static void main(String[] args) {
    String text = "This is my text. Life is great";
    System.out.println(count(text,'i',0));
}

public static int count(String line, char c, int pos) {
    if (pos >= line.length()){
        return 0;
    }

    return compare(line.charAt(pos), c) + count(line, c, pos+1);
}

public static int compare(char a, char b){
    if (a == b){
        return 1;
    } else {
        return 0;
    }
}

Note that thanks to not substringing every time, time complexity is O(n) instead of yours O(n^2)

Upvotes: 2

dckuehn
dckuehn

Reputation: 2475

You never actually increment count. You just keep returning count. At the very end of your recursive stack, count will return 0, as that is what you initialize count to at the begining of every method call, and it will keep returning zero until it gets to the bottom of the stack, then return 0. You need to do this:

charOccurences += count (line, c);
return charOccurences;

so charOccurences will start at 1 at the first occurence, then propagate up.

Upvotes: 1

Related Questions