Recursive palindromus C

Question

My functions are not working properly, always the program tells me that it is not palindromic, for any situation. Follow 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; 
 }

Answer 1

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 recursion understanding, but in the string manipulation. In C, a string is started by the zero index and finished by the character '\0'. Thus, the word of palindromic testing anna has the following characters in the following positions::

[0] -> 'a'
[1] -> 'n'
[2] -> 'n'
[3] -> 'a'
[4] -> '\0'

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

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

The function inverte, it receives 3 parameters:

1. n, which is the string we ask if it is palindromic or not
2. y, whose name I can’t boot means one, but which in code is something like the basis for comparing the right side of the string
3. aux, the auxiliary index running from left to right to determine whether the string is palindromic

On the initial call of inverte, the following values are passed:

1. n ==> the string in question
2. y ==> the size of the string passed as n
3. aux ==> 0, the initial position of the string

The comparison within inverte occurs on the left index (aux) and the right index (y) as follows:

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

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

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

Remembering the initial decomposition I made for the word anna, in position 0 we have the character 'a', whereas in the position 4 we have the character '\0'! Then, substituting for the characters being compared:

if ('\0' != 'a') return 0;

And '\0' is direferent of 'a', so he will leave the function at that point. Always.

Almost whatever string is passed to the function palindromo (which in turn calls the function inverte), it will compare the first character of that string with '\0', which will always be distinct; the only string that this function correctly recognizes as palindrome is the empty string, so the comparison of the first character (end of string, '\0') and the string end gives equal and inverte correctly detects that "" is palindromic. So, our problem is either in the interpretation of the index y or the initial value of y. So I made two suggestions for correction for this.

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

Tip 1: Pass the position of the last valid letter

In this suggestion, I change as the function palindromo flame inverte. Here, the last valid position for the word anna is 3, because it has length 4 and C starts strings at position 0:

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

I see in the Ideone

Suggestion 2: y is the index indicating the character just after the last valid

In that suggestion, I changed the interpretation of y: now, y will always be the index after the last valid character. Then, the palindromo remains identical, but I changed who was being compared in the comparison of inverte:

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

I see in the Ideone

Answer 2

Your code is confused, there’s too much if "loose", one tip is to use the keys {} to separate, in my opinion is better the visualization.

As in the comment you said you’re a little lost in recursion, I’ll show you a way to do it (it’s not the only one). In the code below you enter the word you want and it returns whether or not it is palindrome.

#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 on Ideone.

Using the function int palindromo (char *n) 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 merely modified your function inverte.

See on Ideone.

Answer 3

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

int pali(char palavra[], int tam, int i)
{
    if(i > tam/2)

        return 1;

    if(palavra[i] == palavra[(tam-1)-i])

        return pali(palavra, tam, i+1);

    else return -1;
}

int main()
{
    char palavra[15];
    int tam = 0;

    scanf("%s", &palavra);

    tam = strlen(palavra);

    // retorna 1 caso seja palindromo e -1 caso n seja
    if(pali(palavra, tam, 0) > 0)

        printf("A palavra %s e palindromo", palavra);

    else

     printf("A palavra %s nao e palindromo", palavra);

    return 0;
}