recursive palindrome

[doon]

The word palindrome is derived from the Greek palindromes, meaning running back again . A
palindrome is a word or phrase which reads the same in both directions. Some simple examples
are:
RACECAR DEED LEVEL PIP ROTOR CIVIC POP MADAM EYE NUN RADAR TOOT
Write a C++ function that checks recursively if a sentence is a palindrome (ignoring blanks,
lower- and uppercase differences, and punctuation marks so that “Madam, I'm Adam” is accepted
as a palindrome. Write a main program that tests your function.

[kbw]

That sounds interesting.

[theranga]

work out what to put in your function by working out what it is going to do:

1) removes the spaces and punctuation from a std::string object (your sentence)
2) iterates over every pair of letters (first and last, 2nd and 2nd last, ...) until it reaches the middle
3) for each pair, check if the two letters are equal.
4) If you write the function to be something like this:
bool isPalindrome (string sentence); then if they are not equal, you can just return false;.

5) If it reaches the end of the loop, the string is a palindrome, so the function calls return true;.

Hope this helps you write the code!

[doon]

would you help me?

[theranga]

yes, but it's better if you do most of the work

because then you learn and improve

[doon]

yea but i guess that i have to put a pointer in the first of the sentence and in last of it so how i can do that?

[theranga]

anyway, based on what's above, where would you start?

[doon]

yea that's way better to learn but cuz i need it asap for two hours thats why i have no enough time to understand every single thing but in the next time sure i will

[doon]

bool isPalindrome (string sentence);

[theranga]

ok

#include <string>
using namespace std;

bool test_palindrome (string sentence)
{
    for (int i=0; i<sentence.length(); i++)
    {
        if (sentence[i]!=sentence[sentence.length()-(i+1)]) return false;
    }
    return true;
}

[doon]

well, but that is a loop while in the question they asking for a recursive

[theranga]

the way this works is as above:

- if characters that would be equal in a palindrome (1st and last, 2nd and 2nd last, etc to last and 1st) are not equal, it is not a palindrome, so return false.
- if all the character 'pairs' are equal, it will break the loop without returning, so return true.

Now all you need to do is write a main() function to test it.

[theranga]

recursive as in it (the function) calls itself?

[doon]

yea we use the function which calls itself instead of the loop but how come we use both of them at the same time?

[theranga]

sorry my misunderstanding. I didn't realise what recursion was because i was taught it as 'dynamic programming'.

we don't use both at the same time, they are two different ways to do the same thing.

but anyway, a modified version:

#include <string>
using namespace std;

bool test_palindrome (string sentence)
{
    for (int i=0; i<sentence.length(); i++)
    {
        if (sentence[i]!=sentence[sentence.length()-(i+1)]) return false;
    }
    return true;
}

EDIT:
wrong one, sorry

this is the right one

#include <string>
using namespace std;

bool test_palindrome (string& sentence,int first=0,int last=string::npos)
{
    if (last==string::npos) last=sentence.length()-1;
    if (sentence[first]==sentence[last])
    {
        if ((last-first)<2) return true;
        else return test_palindrome(sentence,first+1,last-1);
    }
    else return false;
}

[kbw]

theranga
Please do not do homework for students. It's bad for them, bad for the forum and doesn't help you.

Helping is fine, but I haven't seem doon post any code, so what you're offering isn't help.

[doon]

would u please explain what did u mean by string::npos ?

[doon]

and why if ((last-first)<2) we are dealing with strings (sentences) i didnt got it?

[theranga]

the default values mean that you can call it as test_palindrome("Trolololol") and it will still work.

now it just needs a function that goes through the string and (a) makes it all lower case and (b) removes all the punctuation

[doon]

aha, what about (a) makes it all lower case and (b) removes all the punctuation