Like Tree8Likes
  • 1 Post By Salem
  • 1 Post By Salem
  • 1 Post By Kyaw Zin Latt
  • 3 Post By Salem
  • 2 Post By iMalc

Palindrome test using recursion.

This is a discussion on Palindrome test using recursion. within the C Programming forums, part of the General Programming Boards category; Hi all, I need some help writing a C program to test a string and see if it is a ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    6

    Exclamation Palindrome test using recursion.

    Hi all,

    I need some help writing a C program to test a string and see if it is a Palindrome by using a recursive function. Any ideas as to how I can go about it?

    Thanks

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    Take an example string
    "never odd or even"

    Compare the first and last letter.
    "never odd or even"

    Recursively check one in from both ends
    "never odd or even"

    Recursively check two in from both ends
    "never odd or even"

    If you get to the middle of the string, you have a palindrome.

    Whether you pass n directly, or do some pointer maths, it's entirely up to you.
    Messi 10 likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    Code:
    #include <ctype.h>
    #include <stdio.h>
    
    #define STR "never odd or even"
    
    static int palindrome(const char *s);
    
    static char *stripspace(char *to, const char *from);
    
    int main(void)
    {
        const char *s[] = { "not palindrome", "palindrome" };
        char buf[1024];
    
        puts(s[palindrome(stripspace(buf, STR))]);
        return 0;
    }
    
    static int length(const char *s)
    {
        return *s == '\0' ? 0 : 1 + length(s + 1);
    }
    
    static int palindrome_(const char *s, const char *e)
    {
        return s > e ? 1 : *s == *e && palindrome_(s + 1, e - 1);
    }
    
    int palindrome(const char *s)
    {
        return *s == '\0' ? 0 : palindrome_(s, s + length(s) - 1);
    }
    
    static void strip(char *to, const char *from, int (*reject) (int))
    {
        if ((*to = *from) != '\0')
            strip(to + !reject((unsigned char) *to), from + 1, reject);
    }
    
    char *stripspace(char *to, const char *from)
    {
        strip(to, from, isspace);
        return to;
    }

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    The point is to let the OP work out an answer for themselves, rather than dump a ready made answer they can copy/paste without knowing what they're doing (or even learn anything about the process of how programs are created).

    You don't become a great cook, simply by reading cookery books, or eating in fine restaurants.
    Messi 10 likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Nov 2012
    Posts
    23
    Quote Originally Posted by Messi 10 View Post
    Hi all,

    I need some help writing a C program to test a string and see if it is a Palindrome by using a recursive function. Any ideas as to how I can go about it?

    Thanks

    Are there restriction about the number of parameters of the function?
    if not, the solution is easier that the posted up there, and the problem can be formulated as follow:

    Write a recursive function that takes as parameter the string, 0, and the lenght of the string-1 and check if a string is palindrome.
    I invite you to try based to the explanation of Salem.
    Hint: Be carefull with the spaces.
    Last edited by root; 11-18-2012 at 03:26 AM.

  6. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    3
    Code:
    #include <stdio.h>
    #include <ctype.h>
    int testPalindrome(char a[50],int i,int strLen);
    
    main(void)
    {
        
        char string[50],a[50];
        int strLen=0,i=0,r=0;
        printf("Enter a sentence: ");
        gets(string);
        while(string[i++]!='\0')
            strLen++;
        
        for(i=0;i<strLen;i++)
        {
            if(isalpha(string[i]))
            {
                a[r++]=string[i];
            }
        }
        if(testPalindrome(a,0,r-1)==1)
            printf("%s is a palindrome\n",string);
        else
            printf("%s is not a palindrome\n",string);
        return 0;
    }
    
    int testPalindrome(char a[50],int i,int strLen)
    {
    
        if(strLen<=1)
            return 1;
        else if(a[i]!=a[strLen])
            return 0;
        else
            testPalindrome(a,i+1,strLen-1);
    }
    Messi 10 likes this.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    I see Kyaw Zin Latt has the same visual impediment as Barney McGrew when it comes to understanding that the point is NOT to spoon-feed answers!

    On the other hand, Kyaw Zin Latt and Messi 10 joined within an hour of each other from the same IP address, so if some blind copy/pasting goes on, there could be some explaining to do.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    @salem:
    The point of using a programming language is to express a computation. I don't see how stepping through the computation in a vague manner, using English, is more helpful than providing source code that actually does what they're trying to accomplish.

    @messi 10:
    If you want to figure out how to implement such a function on your own, I suggest learning to implement the following functions, recursively, first: strlen, strcpy, strcmp (iterative samples of all of these are given in K&R2). Once you can do that, figuring out whether "never odd or even" is a palindrome should be fairly trivial.

  9. #9
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Barney McGrew View Post
    The point of using a programming language is to express a computation. I don't see how stepping through the computation in a vague manner, using English, is more helpful than providing source code that actually does what they're trying to accomplish.
    The question of the OP looks much like homework. The policy on this forum is to help them finding a solution but don't write the programs for them. Both you and Kyaw Zin Latt have just posted your solutions without any further comments. Thus I (and perhaps some others here) have the impression, that you just want to show off your coding capability.

    Bye, Andreas

  10. #10
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    Quote Originally Posted by AndiPersti View Post
    The policy on this forum is to help them finding a solution but don't write the programs for them.
    If they choose to learn nothing from the homework they're assigned and simply claim others' work as their own, it's none of my business. Personally, I find it more educational to read code than to write it.

    Quote Originally Posted by AndiPersti View Post
    Both you and Kyaw Zin Latt have just posted your solutions without any further comments.
    Further comments weren't necessary.

    Quote Originally Posted by AndiPersti View Post
    Thus I (and perhaps some others here) have the impression, that you just want to show off your coding capability.
    Why consider my motivation above the helpfulness of my response?

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Barney McGrew View Post
    Further comments weren't necessary.
    You provided a solution using function pointers to someone who doesn't even know how to start writing a recursive function, or even int main(void) by the looks of it.
    Yeah you're only fooling yourself with that comment.
    Click_here and AndiPersti like this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    If they happened to find that part confusing they could either ask about it or look it up in a C reference. It's not like I'm going to explain every single part of the code that they might potentially find confusing.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. palindrome recursion
    By -EquinoX- in forum C Programming
    Replies: 9
    Last Post: 04-04-2009, 09:43 PM
  2. Test at http://www.artlogic.com/careers/test.html
    By zMan in forum C++ Programming
    Replies: 6
    Last Post: 07-15-2003, 06:11 AM
  3. Test Palindrome
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 01-11-2002, 10:50 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21