Check Palindrome

#include <iostream>
using namespace std;

bool checkPalindrome(string str, int i, int j) {
    // Base case: If the left index crosses the right index, the string is a palindrome
    if(i > j)
        return true;

    // If the characters at the current indices are not the same, it's not a palindrome
    if(str[i] != str[j])
        return false;

    // Recursive call: check the next pair of characters
    return checkPalindrome(str, i + 1, j - 1);
}

int main() {
    string str = "madam"; // Example palindrome
    int n = str.length();
    if(checkPalindrome(str, 0, n - 1))
        cout << str << " is a palindrome." << endl;
    else
        cout << str << " is not a palindrome." << endl;

    return 0;
}

Example Walkthrough:

Let’s see how this function works for the input string “madam”:

1. Initial Call: checkPalindrome(“madam”, 0, 4)

   • i = 0, j = 4
   • Characters: str[0] = 'm', str[4] = 'm' (match)
   • Recursive Call: checkPalindrome("madam", 1, 3)

2. Second Call: checkPalindrome("madam", 1, 3)

   • i = 1, j = 3
   • Characters: str[1] = 'a', str[3] = 'a' (match)
   • Recursive Call: checkPalindrome("madam", 2, 2)

3. Third Call: checkPalindrome("madam", 2, 2)

   • i = 2, j = 2
   • Base case: Since i is not greater than j, we check the characters.
   • Characters: str[2] = 'd', str[2] = 'd' (match)
   • Recursive Call: checkPalindrome("madam", 3, 1)

4. Fourth Call: checkPalindrome("madam", 3, 1)

   • i = 3, j = 1
   • Base case: i (3) is greater than j (1), so it returns true.

5. Returning Back:

   • The calls return true successively until we reach back to the first call.
   • All characters matched, so “madam” is confirmed as a palindrome.

Final Output

madam is a palindrome.