CODEWITHSUNDEEP
javarecursion
user3247128
user3247128

Reputation: 359

In Java how can I figure out how many of a certain letter appears in a string with recursion?

So I need to use recursive programming to figure out how many times a certain letter appears in a word. For example, the word "complete" would have 2 e's. I kind of know what I need to do but I am just not sure how to do it. I currently have a scanner set up to take the word from the user, but that is all I have coded at the moment. I feel like the pseudocode should be something like;

Take word from user

if (letter <= 0)

return 1;

else return length of characters in word

I am guessing that I use the length or charAt method somehow? I really need some guidance here, like how does the recursion come in? Is that because it breaks down the word until it finds the amount of "e's" remaining? Would the base case be 0?I really appreciate the help! I am really new to this. Thank you very much.

Upvotes: 0

Views: 359

Answers (5)

pwillemet
pwillemet

Reputation: 613

Instance of doing this with a recursive method, assuming you store the word in a String word variable :

String word //(your word)

public int howMany(char c, String word) {
    // stop condition
    if(word.length == 0) {
        return 0;
    }


    if(word.charAr(index) == c) {
      return 1 + howMany(c, word.substring(1, word.length));
    }
    else {
      return 0 + howMany(c, word.substring(1, word.length));
    }
}

The trick is to call the method with the world without its first letter, and do it again, and again, until there is no more letter.

Upvotes: 1

Vivin Paliath
Vivin Paliath

Reputation: 95508

Since this is homework, I'll give you hints. Think of it this way:

num_occurrence(char, str) = num_occurrence(char, str[0]) + num_occurrence(char, str[1:])

Now think of what you can do meaningfully in the following cases:

  1. num_occurrence(char, str) where str is an empty string. Can you return a meaningful value for the number of occurrences of char in an empty string?
  2. num_occurrence(char, str) where str is a single letter. What value would you return in this case? It depends on what the character is inside str, right?
  3. num_occurrence(char, str) where str has more than one character. Can you break this down in terms of the above cases?

Upvotes: 1

Manoj Shrestha
Manoj Shrestha

Reputation: 4684

Here's what you can do: 

   public static void main( String[] args ) {

        String myString = "Your test string here...";

        List< Character > alreadyDone = new ArrayList< Character >( );

        for ( Character myChar: myString.toCharArray( ) ) {

            if ( alreadyDone.contains( myChar ) ) {
                continue;
            }

            System.out.println( myChar + ": " + getCount( myString, myChar ) );
            alreadyDone.add( myChar );
        }

    }

    // recursive method to calculate the occurrence of a character in a string

    private static int getCount( String string, char myChar ) {

        if ( string.length( ) == 0 ) {
            return 0;
        }

        if ( string.charAt( 0 ) == myChar ) {
            return 1 + getCount( string.substring( 1 ), myChar );
        }

        return getCount( string.substring( 1 ), myChar );
    }

Upvotes: 1

Patrick87
Patrick87

Reputation: 28292

You'll need to use substring and charAt. Here's the pseudocode:

CountLetter(string, letter)
1. if string.length() == 0 then return 0
2. if string.charAt(0) == letter then
3.     return CountLetters(string.substring(1), letter) + 1
4. else then return CountLetter(string, letter)

Basically, recursive calls should use smaller versions of the string.

Upvotes: 1

Stefan Haustein
Stefan Haustein

Reputation: 18793

The pseudocode probably should be more like this:

  • If the word is empty, return 0
  • If the first letter is an 'e', return 1 + the number of 'e's in the rest of the word
  • Otherwise, return the number of 'e's in the rest of the word.

In Java, you get the rest of the word with word.substring(1). This method of counting is quite inefficient but ok for the purpose of learning recursion.

Upvotes: 0

Related Questions