Check if a String is a Palindrome Using Recursion

Given a string S consisting of lowercase English letters, determine whether it reads the same forwards and backwards using a recursive function that compares the first and last characters and then recurses on the substring between them. Print "YES" if S is a palindrome and "NO" otherwise.

Input: A single line containing the string S. Output: A single line containing "YES" if S is a palindrome, or "NO" otherwise.

1 <= |S| <= 1000. S consists only of lowercase English letters ('a'-'z').

This 'compare outer elements, recurse inward on what's left' technique is the recursive cousin of the iterative two-pointer palindrome check - both express the exact same underlying idea, just with recursion managing the 'shrinking' implicitly via the call stack instead of explicit pointer variables.

Check whether a string is a palindrome by comparing its outer characters and recursing inward. Brute force: Reverse the string and compare it to the original directly - this works but requires building a full reversed copy, when the recursive compare-and-shrink approach can exit early the moment a mismatch is found. Optimised: Comparing only the OUTERMOST characters at each recursive level, and shrinking inward only when they match, lets the recursion STOP IMMEDIATELY at the first mismatch found (rather than fully reversing the string first and comparing afterward) - a natural, efficient framing of the palindrome check as a shrinking recursive comparison.

1. The BASE CASE: a string of length 0 or 1 is trivially a palindrome. 2. Compare the FIRST and LAST characters - if they differ, the string cannot be a palindrome (stop immediately). 3. If they match, recurse on the SUBSTRING with both ends removed - the string is a palindrome exactly when this smaller substring is also a palindrome.

Time: O(n) in the worst case (a genuine palindrome, checked all the way to the middle) - often faster in practice due to early exit on a mismatch. Space: O(n), for the recursion call stack in the worst case.

A string of length 1 is always a palindrome ("YES"). The maximum length is 1000 characters.

Be ready to mention the iterative two-pointer version as an O(1)-extra-space alternative - the recursive version here is specifically for practicing recursive thinking, but production code often prefers the iterative version to avoid stack depth concerns on very long strings.