C Programming Palindrome Question?

Question

I have to do a project for my computer science class and we use C. The project asks us to create a function to determine if a SENTENCE is a palindrome.

Here's a short description directly from the project: You MUST have a recursive function called IsPalindrome() which determines whether the string passed to it is a palindrome. It must work recursively by calling itself with different arguments and may NOT have any loops within it. It should return either TRUE or FALSE, since it is a recursive predicate function. When determining whether a string is a palindrome, you should ignore white space characters, punctuation or any other characters that are not alphabetic. You should consider the upper-case and lower-case versions of the same letter to be the same letter. (i.e. they are equal).

How would I do this?

Thank you!

Answer 1

I've seen palindrome functions here before, but not recursive ones, and the requirement to allow for nonalpha characters and spaces is different, too. I like it!



As to how to do this: since you are required to make it recursive, it seems there's only one general approach: compare characters at the ends, and if they match, recursively call for a comparison of the string between them.



Design the function to take two arguments:

(1) a pointer to the beginning of the string; and

(2) a pointer to just past the end of the string.

There's a string length function in the standard libraries to help you with (2).



(a) If the beginning-pointer is greater than or equal to the end-pointer, return TRUE. (An empty string counts as a palindrome.)



(b) See if the first character is alpha. If not, return the result of a recursive call, with the first pointer advanced one character.



(c) Move the end-pointer back one and see if it points to an alpha character. If not, return the result of recursive call with the present pointers (the back one having moved).



(d) If you get here, you've got two alpha characters. Compare these characters; if they don't match, return FALSE.



-- Note: It's possible this will compare a middle character to itself. That's a valid case, and the next recursive invocation will find an empty string and return TRUE, as it should.



-- Note: This is where you have to worry about upper- and lower-case characters. At this point, I would perform the comparison by XORing the two together and then disregarding the bit that distinguishes between the lower- and upper-case versions of ASCII letters. That is, the two match if

((*begin_ptr ^ *end_ptr) | 0x20) == 0x20

which means that no bits differ between the two characters, other than perhaps the one that indicates they differ in case.



(e) If the compared characters match, return the result of a recursive call, in which you pass a pointer to the string following the first character compared (which begins the portion for the next comparison), and a pointer to the last character compared (which is just past the end of that portion).



You don't have to use my particular method of making the whole comparison nondestructive of the input, but it makes it easier to print out a final result in a pretty format like this:



Madam, I'm Adam!

is a palindrome.



ABCDEFGHIJHGFEDCBA

is not a palindrome.



The method I've described is just the one that comes naturally to a bit-masher. (I've had a career in data communications programming, much of it in C.)

Answer 2

First off, think about the recursive algorithm that you need to implement this, before you even start thinking about writing any code.



Hint: if a sentence is a palindrome, then the first and last letters should be the same, and you can then check the rest of the sentence, from the second to the penultimate character.

Answer 3

Here is a simple palindrome program.



#include

#include

#include

void main()

{

char s[100];

int i,l,a=0;

char * s1;

clrscr();

printf("Enter the text you want to test : ");

scanf("%s",s);

s1=s;

l=strlen(s);

for(i=0;i
{

if(*s1 == *(s1+l-1))

{

a=0;

continue;

}

else

{

a=1;

break;

}

}

if(a==0)

printf("%s is a palindrome ",s);

else

printf("%s is not a palindrome",s);

getch();

}





Build it up!! Good Luck!!