0

I'm trying to do a recursive function with C to check if a word is a palindrome or not (read in both ways).

It's the first time I use this kind of function, but I have a problem, I don't know why it doesn't work, if you could help me, there's my code, thanks :

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

int palindrome(char c[100],int i, int j)
{
    if (j == i)
    {
        return 1;
    }

    // Si le premier et le dernier caractère
    // sont les mêmes alors, on peut commencer les tests
    if(c[i] == c[j])
    {
        // On fais les tests pour chaque caractère de la chaine
        return palindrome(c, i++, j--);
    } else {
        return 0;
    }

    return 0;
}

int main(void)
{
    char chaine[100] = "radar";
    int pal;

    pal = palindrome(chaine, 0, strlen(chaine)); // Returns : 0 -> False / 1 -> True
    printf("%d", pal);
    return 0;
}
Jens
  • 69,818
  • 15
  • 125
  • 179
Theo
  • 3
  • 1
  • 6
  • `s[strlen(s)]` is 0. Why is this important? – Gene Oct 04 '17 at 06:36
  • I don't understand what u mean – Theo Oct 04 '17 at 06:37
  • What I think @Gene means, is that you should not check the string terminator in your comparison. – Some programmer dude Oct 04 '17 at 06:38
  • Why ? How should I do tho ? – Theo Oct 04 '17 at 06:39
  • Think back to when you first started [reading your beginners book](http://stackoverflow.com/questions/562303/the-definitive-c-book-guide-and-list) about arrays and array indexes. You have an array of five characters, with indexes `0`, `1`, `2`, `3` and `4`. Now what does `strlen(chaine)` returns? It returns `5`! Is that a valid index of a character in your string? No. Now take some time to think about how you can make it a valid index of the last character. – Some programmer dude Oct 04 '17 at 06:44
  • Hello @Theo, I can see the answer you have accepted is **wrong** and will segfault if given an even length string. Could you please consider accepting the one that is actually right ? Your post is very high in search results it would be very helpful to anyone searching this question ! – ice-wind Feb 20 '23 at 14:28

4 Answers4

1

The problem is your passing j value as strlen(chaine) instead of strlen(chaine) - 1.

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

int palindrome(char c[100],int i, int j) {
    if (j == i)
        return 1;
    else if(c[i] == c[j])
        return palindrome(c, ++i, --j);
    else
        return 0;
}

int main() {
    char chaine[100] = "radar";
    int pal;
    pal = palindrome(chaine, 0, strlen(chaine) -1 ); // Returns : 0 -> False / 1 -> True
    printf("%d", pal);
    return 0;
}
Abhishek Jain
  • 826
  • 8
  • 20
1

You have several problems with your recursion. First, i++ and j-- pass the values of i and j with the post increment/decrement applied as a side effect after the next call to palindrome has already been made. Instead you need:

        return palindrome (c, i + 1, j - 1);

Next, what happens if chaine has an even number of characters? i never equals j. You need to update your test to break recursion to:

    if (j <= i)
        return 1;

Lastly, you are attempting to read the nul-terminating character when you call palindrome in main() using strlen(chaine), instead you need:

    pal = palindrome (chaine, 0, strlen (chaine) - 1);

Putting that together, you could do something like:

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

int palindrome (const char *c, int i, int j)
{
    if (j <= i)
        return 1;

    if (c[i] == c[j])
        return palindrome (c, i + 1, j - 1);

    return 0;
}

int main (int argc, char **argv) {

    char *chaine = argc > 1 ? argv[1] : "radar";
    int pal;

    pal = palindrome (chaine, 0, strlen (chaine) - 1);

    printf ("chaine : '%s' %s a palindrome\n", chaine, pal ? "is" : "is not");

    return 0;
}

Example Use/Output

$ ./bin/recursive_palindrome
chaine : 'radar' is a palindrome

$ ./bin/recursive_palindrome amanaplanacanalpanama
chaine : 'amanaplanacanalpanama' is a palindrome

$ ./bin/recursive_palindrome catfish
chaine : 'catfish' is not a palindrome

(for the curious, it is "a man a plan a canal panama")

David C. Rankin
  • 81,885
  • 6
  • 58
  • 85
  • You are the only person who noticed `i` and `j` passing each other without ever being equal. Great job ! You get an upvote – ice-wind Feb 20 '23 at 14:24
0

If you can achieve what you are looking for without using recursion do the following. Read the word into a list on and then reverse the word into another list and if they match you have a palindrome.

Rhys Miller
  • 11
  • 3
-1

Modified code :
1) If first index is 0 , then last index should be strlen(chaine) - 1.
2) You were passing same values of i and j in the recursive call , you need to use pre-increment and post-increment operators.

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

int palindrome(char c[100],int i, int j)
{

    if (j == i)
    {
        return 1;
    }

    if(c[i] == c[j]) // Si le premier et le dernier caractère sont les mêmes alors, on peut commencer les tests
    {

        // On fais les tests pour chaque caractère de la chaine
        // increment and decrement first 
        // You were passing same values every time (0 and 4)
        return palindrome(c, ++i, --j);

    }
    else
    {
        return 0;
    }

    return 0;

}

int main()
{

    char chaine[100] = "radar";
    int pal;
    // Last index should be strlen(chaine) - 1
    pal = palindrome(chaine, 0, strlen(chaine)-1); // Returns : 0 -> False / 1 -> True
    printf("%d", pal);

    return 0;

}
Bhawan
  • 2,441
  • 3
  • 22
  • 47