Count Letter recursive method

Question

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

Answer 1

So I think I got my solution. It's maybe not that well but it works. Thanks for your help :)

public class CountLetters {

public static void main(String[] args) {

    print("Bitte geben Sie den Text ein: ");
    String text = readString();
    text = toLowerCase(text, 0);
    print("Bitte geben Sie ein Zeichen ein: ");
    String zeich = readString();
    zeich = toLowerCase(zeich, 0);
    if (zeich.length() > 1) {
        throw new PR1Exception("Bitte nur einen Buchstaben eingeben. ");
    }
    char zeichen = zeich.charAt(0);

    if (zeichen > 0 && zeichen < 65 && zeichen > 90 && zeichen < 97 && zeichen > 123) {
        throw new PR1Exception("Bitte nur Buchstaben eingeben.");
    }
    int anzahl = numberOf(text, zeichen);

    println("-> " + anzahl);

}

static String toLowerCase(String text, int i) {
    String lowerText = "";
    if (i == text.length()) {
        return lowerText;
    } else if (text.charAt(i) < 'a') {
        return lowerText += (char) (text.charAt(i) - 'A' + 'a') + toLowerCase(text, i + 1);
    } else {
        return lowerText += text.charAt(i) + toLowerCase(text, i + 1);
    }
}

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

static int hilfe(String t, char ch, int i, int a) {

    if (t.length() == a) {
        return i;
    } else if (t.charAt(a) == ch) {
        return hilfe(t, ch, i + 1, a + 1);
    } else {
        return hilfe(t, ch, i, a + 1);
    }

}

Answer 2

What

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

// Recursive helper function
static int numberOfRecursive(String text, char characterToCount, int index) {

    if (index == text.length()) // Abort recursion
        return 0;

    if (text.charAt(index) == characterToCount) // check char at index, then check next recursively
        return numberOfRecursive(text, characterToCount, index + 1) + 1;
    else
        return numberOfRecursive(text, characterToCount, index + 1);
}

Why

Most recursive problems require a helper function, that actually performs the recursive part. It will be called from the original function with initial values, here with our text, character and a starting position of 0.

Then, the recursive function needs an abort condition, which I provide by a bound check. We terminate if our recursion reached the end of the string.

Finally the recursive function does some calculation which it bases on a recursive call. Here we add 1 to our result, if the char at our index position is the one to count. If not, we continue counting without adding 1.

I hope I could help.

Answer 3

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.

Answer 4

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

Answer 5

You can use an index variable if it is reached to the end returns 0. Otherwise, return 1 if it is letter or 0.

public class Main {
    public static void main(String[] args) {
        System.out.println(numberOf("Hello World-1234", 'o'));
    }

    private static int numberOf(String text, char characterToCount) {
        if (!text.isEmpty()) {
            return numberOf(text.substring(1), characterToCount) + (text.charAt(0) == characterToCount ? 1 : 0);
        }
        return 0;
    }
}

EDIT: Implementation without substring

public class Main {
    public static void main(String[] args) {
        System.out.println(numberOf("Hello World-1234", 'o'));
    }

    private static int numberOf(String text, char characterToCount) {
        if (text.isEmpty()) {
            return 0;
        }
        char[] chars = text.toCharArray();
        char[] newChars = new char[chars.length - 1];
        System.arraycopy(chars, 1, newChars, 0, newChars.length);

        return numberOf(new String(newChars), characterToCount) + (chars[0] == characterToCount ? 1 : 0);
    }
}

Answer 6

The idea of recursion is that you call the same function/method a lot of times after some conditions. A good approach is to call the same function but reduce the string to check each time.

Class

public class StringUtils {
    
    public int numberOf(String text, char characterToCount) {
       int count = 0;
       if (text.length() != 0) {
           if(text.charAt(0) == characterToCount) { //Only increment when is the same character
               count++; 
           }
           count = count + numberOf(text.substring(1, text.length()), characterToCount); //Do a substring but remove the first character
       }

       return count;
   }
}

Test

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class StringUtilsTest {
    
    @Test
    public void should_count_all_the_ocurrences() {
        
        //Given
        StringUtils utils = new StringUtils();
        String sentence = "</www></palabraRandom></www></palabraRandom></palabraRandom></www>";
        
        //When
        int output = utils.numberOf(sentence, '>');
        
        //Then
        assertEquals(6, output);
    }
    
}