Find number of times a character appears in a word using recursion

3
  

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

     

Input and Output Examples:

     

Entry:

araraquara a
     

Output:

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

#define MAX 30

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

    if(letra == '
araraquara a
'){ 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; }
    
asked by anonymous 08.06.2017 / 05:12

2 answers

5

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

In the code you even need to compare if the character of the text being parsed is a null terminator a>. Comparing with the search characters does not make sense.

Then what index should be used to get the letter of the text to be parsed? You do not have it. There was an attempt to create this variable, but it locally is useless. You have to keep putting it on every 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] == '
int ocorrencias(char palavra[], char letra) {
    int contagem = 0;
    while (palavra[i] == '
#include <stdio.h>
#define MAX 30

int ocorrencias(char palavra[], char letra, int i) {
    if (palavra[i] == '
int ocorrencias(char palavra[], char letra) {
    int contagem = 0;
    while (palavra[i] == '%pre%') {
        contagem += letra == palavra[i];
    }
    return contagem;
}
') 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)); }
') { contagem += letra == palavra[i]; } return contagem; }
') 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)); }

See running on ideone . And no Coding Ground . Also put it in GitHub for future reference .

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

%pre%

You can do it in one or two lines, but I do not think it will make up for it. No one gets lost in this and is faster.

    
08.06.2017 / 05:54
3

First, let's start with this:

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

You can eliminate this repetition of the recursive call you have in if and else like this:

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 still not your problem. To understand your problem, let's see what the value of i is:

int i;

That is, variable i is worthless! This is the main reason why it does not work. Therefore, palavra[i] and palavra[i++] are not expressions that will make sense.

To fix this, what you're trying to do is look at the first letter of the word with letra == palavra[i] and recursively pass the rest of the word with palavra[i++] . Now, the first letter of the word is the one that is in the index zero, and therefore you use palavra[0] instead of palavra[i] . For the rest of the word, you get the address of the second character, that is, &(palavra[1]) . So, this code looks 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 does not work because the part that looks at the end of the string is still wrong:

if(letra == '
if (palavra[0] == '
int ocorrencias(char palavra[], char letra) {
    if (palavra[0] == '
#include <stdio.h>
#include <stdlib.h>

#define MAX 30

int ocorrencias(char palavra[], char letra) {
    if (palavra[0] == '
int ocorrencias(char palavra[], char letra) {
    return palavra[0] == '
if(letra == palavra[i]){
    return 1 + ocorrencias(palavra[i++], letra);
}else{
    return ocorrencias(palavra[i++], letra);
}
' ? 0 : (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra); }
') 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; }
') return 0; return (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra); }
') return 0;
'){ return 0; }

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

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

And your ocorrencias function looks like this:

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

Here's what your complete code looks like:

int i;

See here working on ideone.

Ah, it would still be possible to reduce the function ocorrencias a little more by leaving it in a single line, but then you may think that this is already exaggerated:

return (letra == palavra[0]) + ocorrencias(&(palavra[1]), letra);
    
08.06.2017 / 05:54