Find amount of times a character appears in a word using recursiveness

Question

Develop an algorithm that reads a word (string) a character and return the number of times this character appears in the word. The algorithm must be recursive.

Examples of Input and Output:

Entree:

araraquara a

Exit:

5

#include <stdio.h>
#include <stdlib.h>

#define MAX 30

int ocorrencias(char palavra[], char letra){

    if(letra == '\0'){
        return 0;
    }

    int i;
    //palavra[i+1];

    if(letra == palavra[i]){
        return 1 + ocorrencias(palavra[i++], letra);
    }else{
        return ocorrencias(palavra[i++], letra);
    }
}

int main(){

    char palavra[MAX];
    char letra;

    scanf("%s %c", palavra, &letra);

    int ocorre = ocorrencias(palavra, letra);
    
    printf("%d", ocorre);

    return 0;
}

Answer 1

The code has some problems, but the main thing is that it is not ideal for recursion. Every time you have to pass a recursion control state, the iteration is usually better. This is an exercise to learn how to make the right mechanism for the wrong situation. It is this kind of thing that generates programming addictions.

In the same code you need to compare if the character of the text under analysis is a null Terminator. Comparing to search characters makes no sense.

Then what index should be used to pick up the letter of the text to be analyzed? It doesn’t have that. There was an attempt to create this variable, but it locally is useless. You have to keep passing it on each call. You have to create a new parameter. And this makes the iteration algorithm more efficient and more intuitive.

#include <stdio.h>
#define MAX 30

int ocorrencias(char palavra[], char letra, int i) {
    if (palavra[i] == '\0') return 0;
    return (letra == palavra[i]) + ocorrencias(palavra, letra, i + 1);
}

int main() {
    char palavra[MAX];
    char letra;
    scanf("%s %c", palavra, &letra);
    printf("%d", ocorrencias(palavra, letra, 0));
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

To avoid this you have to use a trick to walk the next character in each recursion, see Victor Stafusa’s answer. Which gets even more confusing. Easier to do so:

int ocorrencias(char palavra[], char letra) {
    int contagem = 0;
    int = 0;
    while (palavra[i] != '\0') contagem += letra == palavra[i++];
    return contagem;
}

I put in the Github for future reference.

You can do it in one or two lines, but I don’t think it’s worth it. Nobody gets lost in this and it’s faster.

Answer 2

First, let’s start with this:

if(letra == palavra[i]){
    return 1 + ocorrencias(palavra[i++], letra);
}else{
    return ocorrencias(palavra[i++], letra);
}

You can delete this repetition of the recursive call you have on if and in the else thus:

int a = (letra == palavra[i]);
int b = ocorrencias(palavra[i++], letra);
return a + b;

And this in turn can be simplified in this:

return (letra == palavra[i]) + ocorrencias(palavra[i++], letra);

But that’s not your problem yet. To understand your problem, let’s see what the value of i:

int i;

That is to say, the variable i is worthless! This is the main reason why it doesn’t work. Soon, palavra[i] and palavra[i++] are not expressions that will have meaning.

To fix this, what you’re trying to do is look at the first letter of the word with the letra == palavra[i] and recursively pass the remainder of the word with palavra[i++]. Now, the first letter of the word is the one at zero, and so you use palavra[0] instead of palavra[i]. For the rest of the word, you take the address of the second character, i.e., &(palavra[1]). So this code stays like this:

return (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra);

And also note that now, the variable i is no longer used and can be deleted.

However, this still doesn’t work because the part that looks at the end of the string is still wrong:

if(letra == '\0'){
    return 0;
}

This checks whether the letter given as input is an empty string. Now, this does not check at all if the word has already finished. So what you wanted was this:

if (palavra[0] == '\0') return 0;

And its function ocorrencias gets like this:

int ocorrencias(char palavra[], char letra) {
    if (palavra[0] == '\0') return 0;
    return (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra);
}

Here’s your complete code:

#include <stdio.h>
#include <stdlib.h>

#define MAX 30

int ocorrencias(char palavra[], char letra) {
    if (palavra[0] == '\0') return 0;
    return (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra);
}

int main() {
    char palavra[MAX];
    char letra;

    scanf("%s %c", palavra, &letra);

    int ocorre = ocorrencias(palavra, letra);
    printf("%d", ocorre);

    return 0;
}

See here working on ideone.

Ah, you could still reduce the function ocorrencias a little more leaving it in a single line, but then you may find that this is already exaggerated:

int ocorrencias(char palavra[], char letra) {
    return palavra[0] == '\0' ? 0 : (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra);
}