Check if a given string is palindrome using recursion.

To determine if a string is a palindrome using recursion, we can use a straightforward approach. The base case checks if the string is empty or has one character, in which case it is a palindrome. Otherwise, we can compare the first and last characters of the string. If they are the same, we can recursively call the function with the substring that excludes these two characters. Here's how the implementation looks:

def is_palindrome(s):
    # Base case
    if len(s) <= 1:
        return True
    # Compare first and last characters
    if s[0] != s[-1]:
        return False
    # Recursive call on the substring
    return is_palindrome(s[1:-1])

This solution works effectively for most cases. The time complexity is O(n), where n is the length of the string, as we are checking each character once. However, keep in mind that recursion adds overhead, which can lead to stack overflow for very long strings.

Continuing from the basic approach, we can optimize the palindrome check by ignoring non-alphanumeric characters and considering case insensitivity. This can be particularly useful for phrases like "A man, a plan, a canal, Panama!". We can preprocess the string to filter out unwanted characters and convert it to a consistent case. Here’s a refined version:

import re

def is_palindrome(s):
    # Preprocess the string: remove non-alphanumeric and convert to lower case
    s = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
    # Base case
    if len(s) <= 1:
        return True
    # Compare first and last characters
    if s[0] != s[-1]:
        return False
    # Recursive call on the substring
    return is_palindrome(s[1:-1])

This version enhances usability and handles more diverse inputs while maintaining the same O(n) time complexity. By preprocessing the string, we ensure that our palindrome check is robust against various formats.

While recursion is a valid approach, it’s also important to consider iterative solutions, especially for performance in languages with limited stack size. An iterative method can avoid recursion overhead. Here’s how we can implement an iterative check:

def is_palindrome(s):
    # Preprocess the string: remove non-alphanumeric and convert to lower case
    s = ''.join(c.lower() for c in s if c.isalnum())
    # Two-pointer technique
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

This solution iteratively checks characters from both ends, moving towards the center. The time complexity remains O(n), making it efficient for larger strings without the risk of stack overflow. This approach is practical in production environments where performance is critical.