recursive palindrome

>>I guess this question is kind of particulary stupid as all we need to do is do a strcmp of s1 and s2, am I right...

Not quite:

ABC is not a palindrome but ABC and ABC would compare to itself just fine.

You are on the right track, comparing first to last. Any idea of how to use recursion for that?

I have to say, though, the question does sound odd. Are you sure that was the actual wording? Checking whether a string is a palindrome of another is identical of checking if the string is a palindrome period.

Assuming the question is simply to write a recursive is_palindrome() function, I recommend you write it in C++.

The assumption that a function in itself checks for palindrome() insinuates that it takes 1 argument, the string itself. It will be easier in C++ by using the std::string class.

if(is_palindrome("TENET"))

so I guess I am just misunderstanding the question... can you give me some more examples so I can understand? so ABC and ABC is a palindrome of each other, but why?

I think the base case here is when the strlen is is one and at that time it returns 1... the recursive case is just call palindrome on the string of s1 with length -1 and string of s2 with length s2.. is this corrrect.. or

No, ABC is not a palindrome.

Definition of a palindrome concerns a single word or sequence.

ABA is spelled the same way forwards and backwards.
ABC is not (CBA)

so what does checks whether one is a palindrome of the other... means??

The question seems poorly worded, or just plain wrong.

I guess it could mean that the s1 is the reverse of s2. But that is not the definition of palindrome. I cannot guess at the meaning of your instructor, but if this is his question, it is a misuse of the word "palindrome."

>>The question seems poorly worded, or just plain wrong.

That's why I am saying that it's stupid in the first place.. I can't work on something that I don't understand my self... :). I'll ask him first and get back here again one I know

Here's his response:

Alula is one example.

Just think of the fact that when you are passing a string to a function you
essentially passing a pointer to a character. So you can pass two pointers
one to the beginning of your string  and one to the end of your string. Then
compare the first character with the last character of the string, then the
second character with the second to last character., etc.


So I guess my approach was right, he just wants us to compare the first letter and last letter of a word recursively.. if that's the case.. how can I do this?? Do I need a length variable here..?

I would assume, based on my experience with computer science education, that the intent is to have you write a function that determines if a single string is a palindrome. That is a classic problem often presented to students learning recursion.

It does not take long to write with Java or C++, only about 8-10 lines. C takes a couple more lines.

He just told you how to write it, sounds like he thinks you will use C and "char *" strings.

Is it a C or C++ specific assignment? Does he require you to use pointers? If not, I would use C++ with std::string

yes that is true... so is the base case here when they have reached the middle of the character in a word? if that's the case, how do I know that it is the middle of the character in a word? what if the word length is even, what if it's odd?

>>Is it a C or C++ specific assignment? Does he require you to use pointers? If not, I would use C++ with >>std::string

It's actually a C specific assignment

hmm.. I think what he meant was easier.. after re-reading his reply again.. I think the palindrome will take two pointers to a char.. say the word is Alula, then s1 will be Alula and s2 will be alulA.. so therefore we just need compare each character by character.. till the end of the character of each word... if that's the case then the base case is when the strlen are both 1...

here's my attempt so far, please let me know what you think

#include <stdio.h> 
#include <string.h>
 
 
void substringMinusOne(char* string){
	/*change Alila to lila here*/
}
 
int palindrome(char* s1, char* s2){
	if (strlen(s1) == 1 && strlen(s2) == 1 && strcmp(s1,s2) == 0)
		return 1;
	else if (strlen(s1) == 1 && strlen(s2) == 1 && strcmp(s1,s2) != 0)
		return 0;
	else
		return 1 * palindrome(substringMinusOne(s1), substringMinusOne(s2)); 
}
 
int main(void) { 
	char* s1 = "Alila";
	char* s2 = "alilA";
	//char* result = substring(s1);
	int result = palindrome(s1, s2);	
	if (result == 1)
		printf("%s is a palindrome of %s\n", s1, s2);
	else
		printf("%s is not a palindrome of %s2\n", s1, s2);
	return 0; 
}

Select allOpen in new window

First, I think you misunderstood your professor's instructions. You are passing 2 pointers, but to the same string. Not 2 different strings. Assume the string ABC

char * s1 = "ABC";

So if s1 points to 'A', then you want s2 to point to 'C'

s2 = s1 + strlen(s1) - 1; // last character


And I see no use for "substringMinusOne()"

Since s1 and s2 are pointers, once you have verified lengths, etc. just pass:

s1+1 and s2-1 to recursive calls of palindrome()

Also, not sure why you as multiplying by 1 in the recursive call.

Lastly, don't use strcmp(), that compares whole strings until null-char, just compare character by character each call to palindrome() then move s1 up and s2 down. If you compare with strcmp(), you are comparing the start of the string forward to the end of the string forward, not what you intend. Instead compare *s1 == *s2, or s[0] == s2[0]

// I would skip the substringMinusOne function and just do
 
else
   return palindrome(s1+1, s2-1); 

Select allOpen in new window

this is my recent code, not sure where it failed:

#include <stdio.h> 
#include <string.h>
 
 
int palindrome(char* s1, char* s2){
	if (strlen(s1) == 1 && strlen(s2) == 1 && strcmp(s1,s2) == 0){ 
		return 1;
	}
	else if (strlen(s1) == 1 && strlen(s2) == 1 && strcmp(s1,s2) != 0)
		return 0;
	else{
		char result[strlen(s1)-1];
		char result1[strlen(s2)-1];
		strcpy(result, s1+1);
		strcpy(result1, s2+1);
		return 1 * palindrome(result, result1); 
	}
}
 
 
int main(void) { 
	char* s1 = "Alila";
	char* s2 = "pentil";
	
	if (palindrome(s1, s2))
		printf("%s is a palindrome of %s\n", s1, s2);
	else
		printf("%s is not a palindrome of %s2\n", s1, s2);
	
	return 0; 
}

Select allOpen in new window

There is no need to use temporary buffers (result and result1). You already have  pointers s1 and s2

So if s1 points to "ABC";

s1+1 points to "BC" of the original string.

Likewise, if s2 points to "C" of the string, then
s2 - 1 points to "BC" of the same string

Its all one string, and are holding points to different addresses. WIth recursion, you just call the function again with incremented and decremented addresses. No need in copying with strcpy, etc.

ok, I am aware of that now.. how about the base case now.. if that's the case

oh and I guess my another question is how do I make a pointer to point to the end of a string?

okay so if the below code is the recursive code, do we need to check for s1[0] == s2[0] before or after the return palindrome(s1+1, s2-1)?

else
   return palindrome(s1+1, s2-1); 

Select allOpen in new window

For each call of palindrome, I would expect safe code to

1) Check valid pointers and whether s2 is > s1. If s1 <= s2, then they are the same location, return true
2) Check if s1[0] == s2[0], if not equal, can't be palindrome, return false
3) if s1 and s2 are at least 1 character address apart (s2 - s1 > 1) then continue by calling palindrome(s1+1, s2-1)

>>oh and I guess my another question is how do I make a pointer to point to the end of a string?

char * s = "ABC";

while(*s != '\0' && *(s+1) != '\0')
    s++;

At the end, s should be pointing to "C"

If you just do:
while(*s)
   s++;

Then s will end up pointing to the null terminator character (right after 'C')

But you really don't want to necessarily use s, you probably want to use a 2nd variable, t.

char * t = s + strlen(s) - 1;

so I initialize both pointers to point at ABC first and then one of them I reversed the pointer to point to the end of the string?

>>so I initialize both pointers to point at ABC first and then one of them I reversed the pointer to point to the end of the string?

How does reversing a pointer work? I've never heard of this term. A pointer is simply a memory address (large integer value).

So if my pointer value was 0xff000000, would reversing it to 0x000000ff make it point to an end of anything?

sorry.. I choosed the wrong term there, I didn't mean to reverse the pointer.. I meant to make the pointer first point to a char ABC and then I make it to point at C, using the while loop you showed above and also I can have another pointer that points to ABC, so both points to different strings...

OK. I understand you used the wrong term.

So after the while loop approach, you end up with 2 pointers that don't really point to different strings, they point to different parts of the same identical string. THis is key to understand due to how your professor wants you to write the solution.

ptr1       ptr2
   |         |
   V        V
   A   B  C


so call:  palindrome(ptr1, ptr)

Then when ptr1 increments, and ptr2 decrements you get

  ptr1  ptr2
       | |
       VV
   A   B  C

(both pointing to B)

ok lets just talk with code then on how to have 2 pointers to point to the same string, but one points to the end of it. Is it something like below?

char* s1 = "ABC"
char* s2 = "ABC";
 
while(*s2 != '\0' && *(s2+1) != '\0')
    s2++;

Select allOpen in new window

We are going around in circles. Your latest code sample uses 2 strings, not 1, so s1 points to the beginning of 1 string, and s2 points to the end of a completely different, but identical string. You can use that in your algorithm because the pointers need to meet in the middle.

char* s1 = "ABC"
 
s2 = s1;
while(*s2 != '\0' && *(s2+1) != '\0')
    s2++;

Select allOpen in new window

so assuming I have s1 and s2 set up.. below is my code...

int isPalindrome(char* s1, char*s2){
   if (s1 <= s2)
      return true;
   else if (s1[0] != s2[0])
      return false;
   else if (s2-s1 > 1)
       return palindrome(s1+1, s2-1);
    }
}

Select allOpen in new window

>>   if (s1 <= s2)
      return true;

Why would you return true if one pointer is less than or equal to the other pointer? Comparing pointers doesn't compare what they point to.  You are just comparing memory addresses, not the content in the memory address.

you said this yourself above:

 If s1 <= s2, then they are the same location, return true

Oops! This confusion is all my fault. Sorry.

I meant if s1 == s2   :(

You want to return if the pointers meet.

But you want to keep the

if(s2 - s1 > 1)

because you don't want to recursively call palindrome with s1+1

And what happens now, after those 3 cases? What if s2 - s1 == 1 ? What does that mean (assuming you fix the 1st if according to my correction)?

>>And what happens now, after those 3 cases? What if s2 - s1 == 1 ? What does that mean (assuming >>you fix the 1st if according to my correction)?

it just means that they are one letter apart, right?

well that, plus the fact that it made it past all of the other if statements means more. If they are 1 letter apart and the letters are equal (since it did not return at the 2nd statement) means it is a palindrome.

so s2 - s1 == 1 is also another base case?

  if (s1 == s2)   // met in the middle, so is palindrome
      return true;
   else if (s1[0] != s2[0])   // 2 characters not equal, is NOT palindrome
      return false;
   else if (s2-s1 > 1) // difference in pointers > 1, still more string to check, so recurse
       return palindrome(s1+1, s2-1);
   else
       return <fill in the blank>;          // None of above ifs() are true, so what does this mean?



PS: technically you aren't checking for the case if someone calls your function with invalid pointers (NULL), or where s1 > s2, that would cause your function to fail by eventually incrementing s1 and or s2 outside of valid address space

so does the fill in the blank just returns false?

Im tempted to tell you, but in the spirit of homework rules I wont. :)

How about testing the function with some actual strings, and put some print statements in there to see what happen either way.

At each if() you have to think in terms of which cases are left after that if. Make sure you have covered all cases.

all I can see the only left is s2-s1 <= 1 right? that's the last else that you mentioned me to fill in the blanks

Yes s2-s1 <= 1, but what does that mean regarding the actual characters equality at that point?

well that basically suggests that it needs to return false, as for example the string is apple and s2 has pointed to l and s1 has pointed to p, which is not right... it should return false

if s2 points to l and s1 points to the first p, then s2-s1 will = 2 (which is not <= 1)

>> well that basically suggests that it needs to return false, as for example the string is apple and s2 has pointed to l and s1 has pointed to p


For that case, your function would have already returned at the 2nd if statement

else if(s1[0] != s2[0])

hmm..so then what's the purpose of this one? i really don't think it's neccessary ...

You have to return something at the end of the function if all other cases fail. Its not a void function.

Like I said, run some test code on different cases, you will find out what happens.

>>You have to return something at the end of the function if all other cases fail. Its not a void function.

I know and the only option is true/false... we don't do another recursive case right there

>>More apologies if this snippet ruins the learning process, I intended only to post this code as a complete solution and to ensure that future viewers have a functional example to work with.

Well, that's exactly what it has done. I could have posted a solution the first time through, I was encouraging kuntilinak to test his "theories" and report back.

This is a homework assignment, so I will ask an admin to review your post.