Problem E
I Hope You're Not Aibohphobic....
Palindromes are words that read the same forward or backward. For example, if you reverse the word civic, it is still civic. Aibohphobia is the irrational fear of palindromes so, in case any of our students suffer from this crippling condition, it is important for us to be able to detect when a word is a palindrome.
Unfortunately, some people in the Department of Computer Science suffer from iteraphobia: the irrational fear of iterative algorithms (the very sight of a for loop makes them run for the hills). So, in deference to the iteraphobes in the department, you must write a program that detects whether a word is a palindrome using a recursive algorithm. Fortunately, palindromes are easy to define recursively. Given a string $s$ with at least one character:

If $s$ has only one character, then it is always a palindrome.

If $s$ has two characters, $c_1c_2$, then it is a palindrome only if $c_1 = c_2$.

If $s$ has more than two characters, we can think of $s$ as $c_1s’c_2$, where $c_1$ is the first character in $s$, $c_2$ is the last character in $s$, and $s’$ is the substring between those two characters. $s$ is a palindrome only if $s’$ is a palindrome and $c_1 = c_2$.
Your solution must use a RECURSIVE function, using the definition presented above.
On the exam, any other type of solution will receive zero points!
EVEN IF KATTIS JUDGES IT AS CORRECT!
Input
The input contains a single word containing only lowercase letters, no whitespace, and with a maximum length of 250 characters.
Output
If the word is a palindrome, print PALINDROME. Otherwise, print NOT PALINDROME.
Sample Input 1  Sample Output 1 

aibohphobia 
PALINDROME 
Sample Input 2  Sample Output 2 

foobar 
NOT PALINDROME 
Sample Input 3  Sample Output 3 

abba 
PALINDROME 