Using recursion to check whether a text string is a palindrome


This program checks whether a text string is a palindrome or not.


The code uses recursive function calls to determine whether the first and last characters of the string are the same. If they are not the same then the string can't be a palindrome, but if they are then the checking function is recursively called again to check the rest of the text.

The chain of recursive calls continues until reaching the middle of the text string, at which point no more functions will be called.

Copy and paste into a text editor, then save as palsource.cpp (or something similar).

To compile from the command-line:

    g++ -o palindrome palsource.cpp

Once compiled, here's how you can run the newly created executable:

    ./palindrome

A few more details can be downloaded from the CAS resources section here. (4 sample pages from the book, compressed to 72dpi.)

Code is below:

#include <iostream>    // Program will be displaying some text on the screen
using namespace std;    // Will be using standard identifiers string, cin, cout

// --------------------

string removeSpacesEtc( string original )
{

    // Makes new copy of original string, but containing only letters of alphabet
    // Any spaces or punctuation will not be included in the new string
    string cleaned = "";

    unsigned int textLength = original.length();
    char currentChar;

    for ( unsigned int pos = 0;  pos < textLength;  pos++ )
    {
        currentChar = original.at( pos );
  // Obtain single character

        // If the character is a letter then convert to upper-case and add to copy
        if ( isalpha( currentChar ) )
            cleaned += toupper( currentChar );      

    }  // end of for loop

    return cleaned;
}


// --------------------

bool isPalindrome( string textToCheck )
{
    // This function determines whether a string value is a palindrome or not.
    // It returns a true value if the string is found to be a palindrome,
    // otherwise returns a false value.

    bool bothSidesSame;
    int textLen = textToCheck.length();

    if ( textLen >= 2 )
    {
        // Examine the first and last characters of the string
        char first = textToCheck.at( 0 );
        char last = textToCheck.at( textLen-1 );


        // If they are the same then determine whether the rest of the string
        // is a palindrome using a recursive call
        if ( first == last )
        {
            bothSidesSame = true;
            if ( textLen > 2 )
                bothSidesSame &= isPalindrome( textToCheck.substr( 1, textLen-2 ) );
        }
        else
            bothSidesSame = false;

    }
    else
        if ( textLen == 1 )
            bothSidesSame = true;
  // String contains a single character - palindrome

    return bothSidesSame;
}


// --------------------

int main()
{
    string sentence;


    // Infinite loop
    while ( true )
    {
        // Allow user to type in a line of text
        cout << "Type in a sentence: " << endl;
        getline( cin, sentence );


        // Remove any character that is not a letter of the alphabet
        sentence = removeSpacesEtc( sentence );


        // Activate the function to check for palindrome and display results
        if ( isPalindrome( sentence ) )
            cout << "The sentence IS a palindrome." << endl;
        else 
            cout << "The sentence is NOT a palindrome." << endl;


        cout << "--------------------";
        cout << endl << endl;


    }  // end of while

    return 0;
}