Recursively counting character occurrences in a string

Question

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.

Answer 1

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);

Answer 2

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)