How Does this Recursive Function Work?

[JesusFreak43]

How can you tell that the first and last letters and each inching letter after that are equal to one another through this program? I don't get the "if (end - begin <= 1). Wouldn't you try and see if begin and end are equal using the "==" operator, not if minusing them is less than or equal to 1? Can someone easily explain this program to me? Thank you. -Alexandra

  template <typename T>
bool palindrome(T begin, T end){
    if (end - begin <= 1 )
        return true;
    
    --end;
    if (*begin != *end)
        return false;
    
    ++begin;
    return palindrome(begin, end);
}

int main() {
    string word;
    
    cin >> word;
    
    if (palindrome(word.cbegin(), word.cend()) == true)
        cout << "word is a palindrome" << std::endl;
    else
        cout << "word is not a palindrome" << std::endl;
}

[mbozzi]

The algorithm works from the outside in. On the first iteration, the first and last letters of the string are compared. On the second iteration, the second and second-to-last letters are compared - we drop the outermost letters off the string after each iteration.

Assuming we don't find a mismatch, we'll eventually be left with a string that's no more than one character long, which is a palindrome by definition.

We might prefer to write that condition in terms of std::distance:

  if (std::distance(begin, end) <= 1)
    return true;

If you prefer to think iteratively, the condition is true when the pointers have met in the middle of the string.

[JesusFreak43]

It seems to be working on palindromes that have other things other than letters in it. How does that work?

Such as a palindrome as: A new order began, a more Roman age bred Rowena.

Wouldn't it hiccup on the comma for instance or in the spaces?

[tpb]

It's only reading in a single word, so it sees the sentence you've shown as just A, which is a palindrome. If you want to read a whole sentence then you should use getline to read an entire line. In that case you would also need to convert both *begin and *end to the same case (toupper(...)) and have it step over punctuation and spaces.

#include <iostream>
#include <string>
#include <cctype> // toupper(), isalpha()
using namespace std;

template <typename T>
bool palindrome(T begin, T end){    

    if (end == begin) return true;

    do --end; while (end != begin && !isalpha(*end));

    while (begin != end && !isalpha(*begin)) ++begin;

    if (begin == end) return true;

    //cout << "Comparing: " << *begin << " and " << *end << '\n';

    if (toupper(*begin) != toupper(*end)) return false;
    
    return palindrome(begin + 1, end);
}

int main() {
    string line;
    
    getline(cin, line);
    
    if (palindrome(line.cbegin(), line.cend()))
        cout << "Input is a palindrome.\n";
    else
        cout << "Input is not a palindrome.\n";
}

[JesusFreak43]

@tpb

So, I have some questions about your code. So, why didn't you do end-1 in the return statement? Is it because --end is in a do/while loop and it will be performed at least once?

Couldn't you have done the same thing with the begin, do a do/while loop instead of having begin+1 in the parameters of palindrome in the return statement?

Why do you have if(end == begin) return true; and if(begin == end) return true;
twice? How do they work when it is running?