Solved

# recursive palindrome

Posted on 2009-04-05
556 Views
I am asked to write a recursive function that takes as input two strings s1, s2 and checks whether one is a palindrome of the other...

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...

am I missing the point of this question? should I just write a recursion that compares the first char of s1 and last character of s2 and start from there? if that's the case can you give me some general idea of how to do this
0
Question by:kuntilanak
• 26
• 24

LVL 40

Expert Comment

ID: 24073387
>>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?
0

LVL 40

Expert Comment

ID: 24073403
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.
0

LVL 40

Expert Comment

ID: 24073432
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"))

0

Author Comment

ID: 24073460
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
0

LVL 40

Expert Comment

ID: 24073512
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)

0

Author Comment

ID: 24073543
so what does checks whether one is a palindrome of the other... means??
0

LVL 40

Expert Comment

ID: 24073570
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."

0

Author Comment

ID: 24073600
>>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
0

Author Comment

ID: 24073606
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..?
0

LVL 40

Expert Comment

ID: 24073611
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.
0

LVL 40

Expert Comment

ID: 24073615
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
0

Author Comment

ID: 24073617
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?
0

Author Comment

ID: 24073621
>>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
0

LVL 40

Accepted Solution

mrjoltcola earned 500 total points
ID: 24073645
Yes, you end with you reach the middle (begin >= end)
That will handle both cases.

So in odd case, your begin will meet end. You don't have to compare the middle to itself.

In even case, you can probably handle it by checking the length of the string before narrowing to substring. If end - begin <= 1, you are done

Or you can use C++ you can use string::substr() and string::length() and you don't have to track 2 parameters, just pass local string objects.
0

Author Comment

ID: 24073659
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...
0

Author Comment

ID: 24073720
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;

}
0

LVL 40

Expert Comment

ID: 24073783
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);
0

Author Comment

ID: 24073808
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;

}
0

LVL 40

Expert Comment

ID: 24073836
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.

0

Author Comment

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

Author Comment

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

Author Comment

ID: 24074091
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);
0

LVL 40

Expert Comment

ID: 24074132
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)
0

LVL 40

Expert Comment

ID: 24074145
>>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;

0

Author Comment

ID: 24077307
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?
0

LVL 40

Expert Comment

ID: 24077477
>>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?
0

Author Comment

ID: 24077769
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...
0

LVL 40

Expert Comment

ID: 24077842
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)
0

Author Comment

ID: 24078163
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++;
0

LVL 40

Expert Comment

ID: 24078530
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++;
0

Author Comment

ID: 24078607
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);

}

}
0

LVL 40

Expert Comment

ID: 24082294
>>   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.

0

Author Comment

ID: 24082570
you said this yourself above:

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

LVL 40

Expert Comment

ID: 24082804
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)?

0

Author Comment

ID: 24082895
>>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?
0

LVL 40

Expert Comment

ID: 24083016
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.

0

Author Comment

ID: 24083064
so s2 - s1 == 1 is also another base case?
0

LVL 40

Expert Comment

ID: 24083171
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
0

Author Comment

ID: 24083219
so does the fill in the blank just returns false?
0

LVL 40

Expert Comment

ID: 24083240
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.
0

Author Comment

ID: 24083287
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
0

LVL 40

Expert Comment

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

Author Comment

ID: 24083381
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
0

LVL 40

Expert Comment

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

LVL 40

Expert Comment

ID: 24083475
>> 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])
0

Author Comment

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

LVL 40

Expert Comment

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

0

LVL 40

Expert Comment

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

Author Comment

ID: 24083939
>>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
0

LVL 40

Expert Comment

ID: 24097969
>>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.

0

## Featured Post

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on thâ€¦
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a â€¦
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor anâ€¦