Problem Statement

Write a program that checks whether a given string is a palindrome or not using recursion.

Examples

Exmple 1:

Input: s = "madam"
Output: true

Explanation: The string "madam" is the same when read from left to right and from right to left.

Example 2:

Input: s = "hello"
Output: false

Explanation: The string "hello" is not palindrome because it reads "olleh" from right to left.

Different Approaches

1️⃣ Recursive Approach

To solve this problem recursively, we need to understand that a palindrome is a string that reads the same forwards and backwards. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the length of the string becomes 0 or 1, indicating that the string is a palindrome.

Solution in C++

#include <iostream>
#include <string>
#include <cctype> // for std::tolower and std::isalpha

// Recursive function to check if a string is a palindrome
bool isPalindrome(const std::string& str, int left, int right) {
    // Base case: If the left index crosses the right index, the string is a palindrome
    if (left >= right) {
        return true;
    }
    
    // Skip non-alphanumeric characters
    while (!std::isalnum(str[left])) {
        ++left;
    }
    while (!std::isalnum(str[right])) {
        --right;
    }
    
    // Check if the characters at left and right indices are equal (ignoring case)
    if (std::tolower(str[left]) != std::tolower(str[right])) {
        return false;
    }
    
    // Recursively call isPalindrome with updated indices
    return isPalindrome(str, left + 1, right - 1);
}

int main() {
    std::string str;

    // Prompt the user to enter a string
    std::cout << "Enter a string: ";
    std::getline(std::cin, str);

    // Call the recursive function to check if the string is a palindrome
    bool palindrome = isPalindrome(str, 0, str.length() - 1);

    // Print the result
    if (palindrome) {
        std::cout << "The string is a palindrome.\n";
    } else {
        std::cout << "The string is not a palindrome.\n";
    }

    return 0;
}

OR (String Containing only characters):

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

// Recursive function to check if the string is a palindrome
bool isPalindrome(string str, int start, int end) {
    // Base case: If the string has 1 or 0 characters, it's a palindrome
    if (start >= end)
        return true;

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

    // Recursively check the remaining substring
    return isPalindrome(str, start + 1, end - 1);
}

int main() {
    string str;
    cout << "Enter a string: ";
    cin >> str;

    // Check if the string is a palindrome
    if (isPalindrome(str, 0, str.length() - 1))
        cout << str << " is a palindrome." << endl;
    else
        cout << str << " is not a palindrome." << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • In each recursive call, we perform a constant amount of work (comparing characters), which can be considered O(1).
  • The number of recursive calls depends on the length of the string, which is proportional to the size of the input string.
  • Therefore. the overall time complexity of the solution is O(n), where n is the length of the input string.
• Space Complexity: O(n)
  • The space complexity of the solution is O(n) as well, considering the recursive calls create a call stack with n frames.