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
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
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.
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.
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; }
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.
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.
Originally Posted by Messi 10
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 04:26 AM.
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); }
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.
@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.
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
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.
Further comments weren't necessary.
Why consider my motivation above the helpfulness of my response?
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.
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"
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.
