Recursive function to calculate the number of lowercase letters in a character string

Question

I was able to do a function to return a given character at an X position of a string:

  public static char funcao (String texto, int indice){

    if (indice == 0){

      return texto.charAt(indice);

    } else {

      funcao(texto, indice - 1);

      return texto.charAt(indice);

    } // fim do if

  } // fim da funcao

then I did another function to check if the letter in that position is minuscule:

  public static int funcao2 (char letra){

    if ((letra >= 'a') && (letra <= 'z')){

      return 1;

    } else {

      return 0;

    }

  } // fim da funcao2

At the end my test on main was like this:

  public static void main(String[] args) {

    String texto = "aBcdEFGHiJ@1-";

    // quantidade de letras minusculas na String
    int quantLetras = 0;

    for (int indice = 0 ;
         indice <= texto.length() - 1 ;
         indice = indice + 1 ) {

      quantLetras = quantLetras + funcao2(funcao(texto, indice));

      //IO.println ("\nLetra: " + funcao(texto, indice));

    } // fim do for

    IO.println ("\nQuandidade de minusculas: " + quantLetras);

  } // fim do metodo principal

In the end the program worked, but it bothers me the way I made it work, etc... There would be a way to do this minuscule letter calculation in a better way with recursiveness?

Answer 1

^{The easiest way is to scroll through the characters of String with a for simple, but if you really want to do recursive, come on...}

---

First of all, this function is not exactly recursive:

public static char funcao (String texto, int indice){    
    if (indice == 0){    
        return texto.charAt(indice);    
    } else {    
        funcao(texto, indice - 1);    
        return texto.charAt(indice);    
    }
}

I mean, you even call the function within itself, but you don’t use the result of this call for anything.

The line funcao(texto, indice - 1); calls the function, but its return is not assigned to any variable, which makes this call useless. And in the end you call texto.charAt(indice), which is exactly the same as what is done inside the if (indice == 0). That is, this function always returns texto.charAt(indice).

There is no reason to take the character of the position X recursively, because the method charAt already returns this character directly. We can then discard this function.

---

To recursively check the characters of a String are lower case letters, we can consider the following:

• if the String is empty, the result is zero
• if the String is not empty, the result is the sum of two things:
  • 1 or 0 (depending on whether the first character is lowercase or not)
  • the total of lower case characters of the remainder of String (from the second character onwards)

An example: if the String for Abc and apply the above algorithm, as would be?

• to String is empty? No, then let’s go to the next step
• the first character (A) is it tiny? No, so the partial result is zero.
• now I check the rest of the String (bc)
  • the first character (b) is it tiny? Yes, so the partial result of this step (that is, of the piece bc) is 1
  • now I check the rest of the String (c)
    • the first character (c) is it tiny? Yes, so the partial result of this step (that is, of the piece c) is 1
    • now I check the rest of the String (to String empty, because no more characters)
    • as the String is empty, the partial result of this step is zero.

Adding up the partial results of each step, the result is 2.

---

The code would look like this:

public static int contaLetrasMinusculas(String texto) {
    // se a String for vazia, retorna zero
    if (texto.isEmpty()) {
        return 0;
    }

    // verifica se o primeiro caractere da String é minúsculo
    char primeiro = texto.charAt(0);
    // se for minúsculo, "c" é igual a 1, senão é zero
    int c = Character.isLowerCase(primeiro) ? 1 : 0;

    // retorna "c" + a contagem do restante da string
    return c + contaLetrasMinusculas(texto.substring(1));
}

Some examples of use:

System.out.println(contaLetrasMinusculas("")); // 0
System.out.println(contaLetrasMinusculas("A")); // 0
System.out.println(contaLetrasMinusculas("b")); // 1
System.out.println(contaLetrasMinusculas("aBcdEFGHiJ@1-")); // 4

Of course you can make it more succinct, but then you see if it becomes less readable/ more difficult to understand:

public static int contaLetrasMinusculas(String texto) {
    if (texto.isEmpty()) {
        return 0;
    }

    return (Character.isLowerCase(texto.charAt(0)) ? 1 : 0)
           + contaLetrasMinusculas(texto.substring(1));
}

---

Unicode

The above code works well for our alphabet. But to work with any Unicode characters, we must make some modifications. For more details on how Unicode works, I recommend oracle tutorial and this question.

In general, Unicode allows characters that do not fit in one char (and are stored internally in two chars - the so-called surrogate pair). So use this approach of charAt does not work for these characters.

And instead use char, we use codepoints (which is the numeric code that all characters have within Unicode).

If you want a more general solution that works with any Unicode characters, the code looks like this:

static int contaLetrasMinusculas(String texto) {
    if (texto.isEmpty()) {
        return 0;
    }

    // primeiro Unicode codepoint da String
    int primeiro = texto.codePointAt(0);
    int c = Character.isLowerCase(primeiro) ? 1 : 0;
    // Character.charCount verifica se o codepoint ocupa um ou dois chars
    return c + contaLetrasMinusculas(texto.substring(Character.charCount(primeiro)));
}

The code keeps working for the previous cases:

System.out.println(contaLetrasMinusculas("")); // 0
System.out.println(contaLetrasMinusculas("A")); // 0
System.out.println(contaLetrasMinusculas("b")); // 1
System.out.println(contaLetrasMinusculas("aBcdEFGHiJ@1-")); // 4

But now it also works for other Unicode characters, such as (DESERET SMALL LETTER LONG I), which corresponds to Unicode Codepoint 66600 and is considered lowercase:

// DESERET SMALL LETTER LONG I http://www.fileformat.info/info/unicode/char/10428/index.htm
String s = new String(Character.toChars(66600));
System.out.println(contaLetrasMinusculas("aA" + s + "Bb")); // 3

Answer 2

Your code is quite confusing for a recursive solution. To solve the problem we have done the following:

• We adopt as a stop condition a text of size 1;
  • If Character is uppercase returns 1, otherwise returns 0;
• For each call we will divide the text into 2 halves, until we reach the specified stop condition. (Similar to what happens in the first stage of mergesort)

The code is as follows::

public int minusculas(String texto) {
    int length = texto.length();
    if(length == 0) {
        return 0;
    }
    if(length == 1) {
        return Character.isLowerCase(texto.charAt(0)) ? 1 : 0;
    } else {
        return minusculas(texto.substring(0, length/2)) + minusculas(texto.substring(length/2, length));
    }
}

Here we have the stacktrace of the algorithm execution:

Texto: aBcdEFGHiJ@1-    esq: aBcdEF dir: GHiJ@1-    
Texto: aBcdEF           esq: aBc    dir: dEF
Texto: aBc              esq: a      dir: Bc
Texto: Bc               esq: B      dir: c
Texto: dEF              esq: d      dir: EF
Texto: EF               esq: E      dir: F
Texto: GHiJ@1-          esq: GHi    dir: J@1- // Começa a avaliar o lado direito
Texto: GHi              esq: G      dir: Hi
Texto: Hi               esq: H      dir: i
Texto: J@1-             esq: J@     dir: 1-
Texto: J@               esq: J      dir: @
Texto: 1-               esq: 1      dir: -

The result will be 4.