Recursive Palindrome

[girlscout]

Just finished this assignment. Head Hurts. Code works. Any tips on cleaning it up or being more effective are greatly appreciated. Thanks in advance.

/*
  Assignment 7 Recursion

"A palindrome is a string that reads the same both forward and backward. 
For example, the string “madam” is a palindrome. Write a program that uses 
a recursive function to check whether a string is a palindrome. Your program 
must contain a value-returning recursive function that returns true if the string 
is a palindrome and false otherwise. Do not use any global variables; 
use the appropriate parameters."

*/




#include <iostream>
#include <string>

using namespace std;



bool isPalindrome(string message)

{
	if (message.length() < 2)     
	{
		return true;
	}
	
	if (message[0] != message[message.length() - 2])
	{
		return false;
	}

	string substring = message.substr(1, message.length() - 2);
	if (!isPalindrome(substring))

	{
		return false;
	}

	return true;
}

int main()

{

	string message;

	cout << "Type a sentence or word to see if it's a palindrome: ";

	cin >> message;

	if (isPalindrome(message))

		cout << " : No palindrome found." << endl;

	else

		cout << " : Palindrome found." << endl;

	
	



	// this next part is only added because for some reason my VS closes out my "build" early; this resets any flag errors 

	cin.clear(); 
	cin.ignore(32767, '\n'); 
	cin.get(); 
	return 0;

}

[icy1]

Hmm, something's off. Try to set up more test cases; probably avoid user input for now so that you can test things faster:

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string message)
{
	if (message.length() < 2)     
	{
		return true;
	}
	
	if (message[0] != message[message.length() - 2])
	{
		return false;
	}

	string substring = message.substr(1, message.length() - 2);
	if (!isPalindrome(substring))

	{
		return false;
	}

	return true;
}

int main()
{
    vector<string> examples = 
    {
        "",
        "a",
        "Hello, world!",
        "A man, a plan, a canal--Panama!",
        "civic",
        "racecar",
        "rotator",
        "rotor",
    };
    
    cout << boolalpha;
    for (auto& e : examples)
        cout << setw(33) << right << e << " : " << isPalindrome(e) << endl;

	return 0;

}

                                  : true
                                a : true
                    Hello, world! : false
  A man, a plan, a canal--Panama! : false
                            civic : false
                          racecar : false
                          rotator : false
                            rotor : false

[tpb]

You could do it without so many string copies (without any copies actually).

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool ispalin(const string &s, size_t i = 0) {
    if (i >= s.size() / 2) return true;
    if (toupper(s[i]) != toupper(s[s.size() - i - 1])) return false;
    return ispalin(s, i + 1);
}

int main() {
    string message;
    cout << "Type a sentence or word to see if it's a palindrome: ";
    cin >> message;
    if (!ispalin(message))
        cout << "no ";
    cout << "palindrome found.\n";
    return 0;
}

[icy1]

@tpb, Yep, I just finished it in similar style. You could structure it with indices, much like you would with a while loop. Just have solid base cases and you could have const ref of the string, which never changes anyway.

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

// i - index from the left
// j - index from the right
bool IsPalindrome(const string& s, int i, int j)
{
    if (s.size() <= 1)
        return true;
    
    if (i >= j)
        return true;
        
    return s[i] == s[j] && IsPalindrome(s, i+1, j-1);
}

int main()
{
    vector<string> examples = 
    {
        "",
        "a",
        "Hello, world!",
        "A man, a plan, a canal--Panama!",
        "civic",
        "racecar",
        "rotator",
        "rotor",
    };
    
    cout << boolalpha;
    for (auto& e : examples)
        cout << setw(33) << right << e << " : " << 
                IsPalindrome(e, 0, e.size()-1) << endl;

    return 0;
}

can test at https://repl.it/repls/FlakyAbsoluteBusinesssoftware

[tpb]

It takes a little extra machinery to skip arbitrary non-alphabetics.

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cctype>
using namespace std;

bool ispalin_r(const string &s, size_t start, size_t end) {
    while (start < end && !isalpha(s[start])) ++start;
    while (end > start && !isalpha(s[end  ])) --end;
    if (start >= end) return true;
    if (toupper(s[start]) != toupper(s[end])) return false;
    return ispalin_r(s, start+1, end-1);
}

bool ispalin(const string &s) {
    if (s.size() == 0) return true;
    return ispalin_r(s, 0, s.size() - 1);
}

int main() {
    vector<string> examples = {
        "",
        "a",
        "Hello, world!",
        "A man, a plan, a canal--Panama!",
        "civic",
        "racecar",
        "rotator",
        "rotor",
    };
    
    cout << boolalpha;
    for (auto& e : examples)
        cout << setw(33) << right << e << " : " << 
                ispalin(e) << endl;

    return 0;
}

[icy1]

@girlscout -- oh, you only had a tiny typo on your 31st line! There you're comparing first to last, so it should read if (message[0] != message[message.length() - 1])
(and not -2). Your approach is logical too, just that there are lots of string copies happening.

[girlscout]

@icy1 Ah!! Thank you! haha I hadn't even noticed and have just been racking my mind.

[girlscout]

@tpb You make it look way more simple, but that's a bit beyond me atm. Very cool to see though. Thanks for your input.