Recursive Palindrome C

2

My functions are not working correctly, the program always tells me that it is not palindrome, for any situation. Here is the code:

#include<stdio.h>
#include<string.h>


int inverte (char *n, int y, int aux) {

     if (y <= aux) return 1;

     else {
         if (n[y] != n[aux]) return 0;

         return inverte(n, y-1, aux+1);
     } 
}

 int palindromo (char *n) {
     int aux1, x = 0;

     aux1 = inverte(n, strlen(n), x);

     if (aux1 == 1) printf("Eh palindromo");

     else printf("Nao eh palindromo");

 }


 int main() {

     char m[30] = {"anna"};

     palindromo(m);

     return 0; 
 }
    
asked by anonymous 16.01.2017 / 13:16

2 answers

3

Taisbevalle's response is beautiful, but I felt it did not touch where Marcelo de Sousa made his mistake.

Strings

Basically, the problem was not in the understanding of recursion, but in the manipulation of the string. In C, a string starts with zero and ends with the character 'anna' . Thus, the palindrome test word strlen has the following characters in the following positions:

[0] -> 'a'
[1] -> 'n'
[2] -> 'n'
[3] -> 'a'
[4] -> '
if (n[y] != n[aux]) return 0;
'

The fifth character is the string terminator, needed in C to indicate its end .

The function anna counts how many characters there are in a given string. strlen("anna") is clearly 4 characters. Then, the return of inverte is 4.

The function n , it receives 3 parameters:

  • y , which is the string that we asked whether it is palindrome or not
  • aux , whose name I can not get a means to, but that in the code is something like the basis for doing the comparison on the right side of the string
  • inverte , the auxiliary index that is traversed, from left to right, to determine if the string is palindrome
  • In the initial call of n , the following values are passed:

  • y == > the string in question
  • n == > the length of the string passed as aux
  • 0 == > inverte , the starting position of the string
  • The comparison within aux occurs on the left index ( y ) and the right index ( anna ) as follows:

    if (n[4] != n[0]) return 0;
    

    Returning to the anna case; the size of y is 4, then the initial value of anna is 4. In the first step of recursion, the values being compared are as follows:

    if ('
        #include<stdio.h>
        #include<string.h>
    
    
        int inverte (char *n, int y, int aux) {
            if (y <= aux) return 1;
            else {
                if (n[y] != n[aux]) return 0;
    
                return inverte(n, y-1, aux+1);
            } 
        }
    
         int palindromo (char *n) {
            int aux1, x = 0;
    
            aux1 = inverte(n, strlen(n) - 1, x);
    
            if (aux1 == 1) printf("Eh palindromo\n");
            else printf("Nao eh palindromo\n");
    
         }
    
    
         int main() {
            palindromo("banana");
            palindromo("anna");
            palindromo("ana");
            palindromo("bananab");
            palindromo("aa");
            palindromo("a");
    
            return 0; 
         }
    
    ' != 'a') return 0;

    Remembering the initial decomposition I did for the word 0 , in position 'a' we have the character 4 , while in the '''a''' position we have the character palindromo ! So, overriding the characters being compared:

    #include<stdio.h>
    #include<string.h>
    
    
    int inverte (char *n, int y, int aux) {
        if (y <= aux) return 1;
        else {
            if (n[y - 1] != n[aux]) return 0;
    
            return inverte(n, y-1, aux+1);
        } 
    }
    
     int palindromo (char *n) {
        int aux1, x = 0;
    
        aux1 = inverte(n, strlen(n), x);
    
        if (aux1 == 1) printf("Eh palindromo\n");
        else printf("Nao eh palindromo\n");
    
     }
    
    
     int main() {
        palindromo("banana");
        palindromo("anna");
        palindromo("ana");
        palindromo("bananab");
        palindromo("aa");
        palindromo("a");
    
        return 0; 
     }
    

    And inverte is 'inverte' , so it exits the function at that point. Always.

    Whatever the string passed to the function "" (which in turn calls the function y ), it will compare the first character of this string with y , which will always be different (note: if the string passed is empty, this does not occur and palindromo correctly detects that inverte is palindrome. So our problem is either in the interpretation of the index anna or in the initial value of 3 . So I made two correction suggestions for that.

    Note that in the suggestions I've added some more test cases.

    Tip 1: move the position of the last valid letter

    In this suggestion, I change how the y function calls y . Here, the last valid position for the word y is palindromo , since it has length 4 and C starts strings at position 0:

    [0] -> 'a'
    [1] -> 'n'
    [2] -> 'n'
    [3] -> 'a'
    [4] -> '
    if (n[y] != n[aux]) return 0;
    
    '

    See the Ideone

    Tip 2: inverte is the index that indicates the character just after the last valid

    In this suggestion, I changed the interpretation of %code% : now, %code% will always be the index after the last valid character. So the call of %code% remains the same, but I changed who was being compared in the %code% :

    if (n[4] != n[0]) return 0;
    

    See the Ideone

        
    25.05.2017 / 12:48
    2

    Your code is confusing, it has a lot of if "loose", a tip is to use the {} keys to separate, in my opinion the visualization is better.

    As in the comment you said that you are somewhat lost in the recursion, I'll show you a way to do it (it's not the only one). In the code below you type the word you want and it returns whether it is palindrome or not.

    #include <stdio.h>
    #include <string.h>
    
    // Função recursiva para verificar se a palavra é palíndromo
    int palindromo(char palavra[], int tam, int posicao) {
    
        if (posicao < tam / 2){
            if (palavra[posicao] == palavra[tam - posicao - 1]){
                return 1 * palindromo(palavra, tam, posicao+1);
            }
            else{
                return 0;
            }
        }
        else{
            return 1;
        }
    }
    
    int main() {
    
       char palavra[255];
       int tam;
    
       printf ("Digite a palavra: \n");   
       gets(palavra); // Ler a palavra digitada pelo usuário
    
       tam = strlen(palavra); // Tamanho da palavra
    
       if (palindromo(palavra, tam, 0))
          printf("É palíndromo\n");
       else
          printf("Não é palíndromo\n");
    
       return 0;
    }
    

    See working at Ideone .

    Using the int palindromo (char *n) function you can do according to the code below:

    #include <stdio.h>
    #include <string.h>
    
    // Função recursiva para verificar se a palavra é palíndromo
    int inverte(char *n, int tam, int posicao){
    
        if (posicao < tam / 2){
            if (n[posicao] == n[tam - posicao - 1]){
                return 1 * inverte(n, tam, posicao+1);
            }
            else{
                return 0;
            }
        }
        else{
            return 1;
        }
    }
    
    int palindromo(char *n) { 
    
        int aux1, x = 0;
    
        aux1 = inverte(n, strlen(n), x);
    
        if (aux1 == 1) printf("Eh palindromo");
        else printf("Nao eh palindromo");
    
    }
    
    int main() {
    
        char m[30] = {"teste"};
        palindromo(m);
    
        return 0;
    }
    

    I just modified your inverte function.

    See the Ideone .

        
    16.01.2017 / 13:40