Write a program that reads a string of characters and calls a recursive function to determine if the letters in the string form a palindrome

Question

I'm tasked with a project to write a recursive function that will determine if a user inputted string is a palindrome or not. I think I have a very strong foundation of code for the problem, but it doesn't seem to work how I want it to.

I was doing some troubleshooting to figure out what was wrong and it appears that if my string is <= 8 characters long the length of the array automatically becomes 14 for some reason. Could use some troubleshooting and input from people better at c++ than myself.

Here is my code:

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

bool isPalindrome(char[], int, int);

int main()
{
    char palin[100],
        lowerPalin[100];

    cout << "Enter a line that might be a palindrome:" << endl;
        cin.get(palin, 100);

    for (int i = 0, x = 0; i < strlen(palin); i++) // this for loop will remove punctuation, white space and make it all lowercase
    {
        if((palin[i] != ' ') && (ispunct(palin[i]) == false))
        {
            lowerPalin[x] = tolower(palin[i]); // transfering inputted array into new array with just alpha characters
            x++;
        }
    }

    int low = 0,
        high = strlen(lowerPalin);

    if (isPalindrome(lowerPalin, low, high))
        cout << "The string is a palindrome." << endl;
    else
        cout << "The string is NOT a palindrome." << endl;

    return 0;
}

bool isPalindrome(char lowerPalin[], int low, int high)
{
    if (lowerPalin[low] == lowerPalin[high])
        return isPalindrome(lowerPalin, low + 1, high - 1);

    if (lowerPalin[low] != lowerPalin[high])
        return false;

    return true;
}

I'm still trying to learn recursion as well, so if anything is wrong with my bottom function please let me know.

EDIT: Thank you all for the help! I was able to understand and fix my mistake thanks to you all. Also thanks for all the tips in your answers, it helps a new student, like myself, a lot!

You forgot to null-terminate `lowerPalin`. – user4581301 Sep 08 '21 at 23:44 — user4581301, Sep 08 '21 at 23:44
high = strlen(lowerPalin) **- 1**; – Jeffrey Sep 09 '21 at 03:31 — Jeffrey, Sep 09 '21 at 03:31

Vlad Feinstein · Answer 1 · 2021-09-09T00:20:51.370

if anything is wrong with my bottom function please let me know.

You need to terminate your recursion if high goes below low.

As written, in case of the palindrome you would go out-of-bounds on your lowerPalin

UPDATE:

As @user4581301 commented below (and in response to your question above), you need to zero-terminate your lowerPalin after populating it from the palin. Otherwise, strlen will be looking for that 0 in the uninitialized array; it may find it at position 14 (as happened to you) or not at all. THAT may cause an access violation exception!

user4581301 · Accepted Answer · 2021-09-09T15:16:02.203

Assumption : you're being forced to use recursion, character arrays, and not allowed to use the functions in <algorithm> that pretty much do all the work for you.

The bug: lowerPalin was not null terminated. That makes high = strlen(lowerPalin); a fatal mistake. strlen counts characters untill it finds a null, so without a null, Crom only knows what strlen will return. If it ever does.

Solution

int x = 0; // need to keep x live after the loop in order to ensure null-termination
for (int i = 0; i < strlen(palin); i++) // this for loop will remove punctuation, white space and make it all lowercase
{
    if ((palin[i] != ' ') && (ispunct((unsigned char)palin[i]) == false))
    {
        lowerPalin[x] = tolower((unsigned char)palin[i]); 
        x++;
    }
}
lowerPalin[x] = '\0'; // null terminate the string or it's not a string. 
                      // It's just a bunch of characters and `strlen` can't 
                      // be trusted.

That said, as soon as x outlives the loop, you don't need strlen. high = x; and done. Sort of. See below for why it's not really this easy.

Modified code with corrections and general commentary embedded as comments

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

bool isPalindrome(char[], int, int);

int main()
{
    char palin[100], lowerPalin[100];

    cout << "Enter a line that might be a palindrome:" << endl;
    if (!cin.get(palin, 100)) // always test the stream state for success
    {
        cout << "bad input, dude." << endl;
        return -1;
    }

    int x = 0; // need to keep x alive after the loop in order to get length of string

    // a different way to iterate the string that doesn't rely on strlen
    for (char * chp = palin; // get pointer to first character in array
         *chp != '\0'; // loop until we find the null terminator
         ++chp) // advance pointer to next character
    {
        if ((*chp != ' ') && (ispunct((unsigned char)*chp) == false))
        {
            lowerPalin[x] = tolower((unsigned char)*chp);
            // This one is weird. tolower's parameter is an int, not a char, and
            // you can have unfortunate results if sign extension takes place.
            // always make sure you use unsigned char with ispunct and any of 
            // the other ctype functions. 
            x++;
        }
    }
    int low = 0, high = x-1; // We know the size of the string thanks to x
                             // but we don't really want the length of the
                             // string. we want the position of the last
                             // character in the string.

    if (isPalindrome(lowerPalin, low, high))
    {
        cout << "The string is a palindrome." << endl;
    }
    else
    {
        cout << "The string is NOT a palindrome." << endl;
    }
    return 0;
}

bool isPalindrome(char lowerPalin[], int low, int high)
{
    if (low >= high) // when high and low meet or pass, we're done looking.
    {                // everything has been compared
        return true; // if we got here, it's a palindrome.
    }
    if (lowerPalin[low] == lowerPalin[high])
    {  // Found a match. Keep looking
        return isPalindrome(lowerPalin, low + 1, high - 1);
    }
    return false; // no match. stop looking
}

For consistency, I would either remove redundant `else` in `isPalindrome`, or change the second `if` to `else if` — Vlad Feinstein, Sep 09 '21 at 00:37
@VladFeinstein Good point. Lemme got back through and add all the optional braces, too. — user4581301, Sep 09 '21 at 00:54
Oh, no! Not superfluous braces! :) I would rather post-increment `x` in `lowerPalin[x] = ...` and loose a couple — Vlad Feinstein, Sep 09 '21 at 00:57
I thought about `owerPalin[x++] = ... `, but didn't because I planned on adding a comment to the `x++;` line. Clearly I didn't and can't remember what I wanted to say. Easier for a beginner to read spaced out like this anyway. — user4581301, Sep 09 '21 at 01:00

JDługosz · Answer 3 · 2021-09-09T00:18:17.390

Learning C++:

Consider your function bool isPalindrome(char lowerPalin[], int low, int high). You are passing in the base address of the character array, plus two positions. You should do this with two pointers instead, needing two parameters instead of 3.

However, we normally deal with begin/end iterator pairs using the convention that the end is one-past-the-end, and following that convention will be less confusing to readers and can be done with a slight change to how they are handled.

However, string_view specifically supports eating away at both ends, so see my version below.

if (lowerPalin[low] != lowerPalin[high])
        return false;

    return true;

Just write: return lowerPalin[low] == lowerPalin[high];
that is, understand that boolean operations are like any other, and not limited to only being used in if statements.

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

 for (int i = 0, x = 0; i < strlen(palin); i++) // this for loop will remove punctuation, white space and make it all lowercase

You are calling strlen every time through the loop, though it should not change.

You are using a fixed size buffer for characters, rather than a std::string.

To iterate over the characters in a string, use a range-based for loop rather than indexing. Your loop using two separate input and output indexes is confusing.

(ispunct(palin[i]) == false) Oh, the cringe, in hurts!
Don't test against true and false. Just be it.

Consider:

// remove punctuation and convert to lower case
std::string condition_input (string_view input)
{
   std::string result;
   for (char c : input) {
      if (c==' ' || ispunct(c))  continue;  // skip these
      result.push_back (tolower(c));
   }
   return result;
}

Your bug (not terminating the output) simply is not possible here, and it is not something you need to worry about at all! That's a far better thing than fixing the bug in the code you have.

In C++, don't declare multiple variables in the same declarator statement, especially if they have decorations like arrays and stars.

recursive test

bool is_palendrome (string_view s)
{
    if (s.length() <= 1)  return true;
    if (s.back() != s.front())  return false;
    s.remove_prefix(1);
    s.remove_suffix(1);
    return is_palendrome(s);  // or could just loop 
}

(and yes, you really can have emoji in your comments)
Notice that back and front are very understandable and it is clear what the code is doing. There are no indexes to keep track of.
Doing the "base" tests first allows the rest of the code to have assumptions: after the first line, we know the string has at least 2 characters. There's no test for meeting or crossing indexes, no place for an index to get out of range or otherwise misused. The code is visibly correct and there's no place for such subtle bugs to hide.

`lowerPalin[high]` will be out of incorrect if `high = strlen(lowerPalin)` even after `lowerPalin` is corrected. — user4581301, Sep 09 '21 at 00:11

Write a program that reads a string of characters and calls a recursive function to determine if the letters in the string form a palindrome

3 Answers3

recursive test