A string s is given, the task is to check if s is a Palindrome or not using recursion.

A string is said to be palindrome if reverse of the string is same as string itself.

##### Example 1: Check if "apple" is a palindrome.

**Input:** "apple"

**Output:** false

##### Example 2: Check if "appa" is a palindrome.

**Input:** "appa"

**Output:** true

##### Example 3: Check if "abcdedcba" is a palindrome.

**Input:** "abcdedcba"

**Output:** false

## Solutions

### Method 1: Recursion

Here we will compare first and last characters and recur for remaining substring. If string has only one character it is an palindrome, this will make the base condition.

##### Complexity

In every fn call, we are increasing start index and decreasing end index, that means fn is called n/2 or n/2+1 times for a string of size n; so Time Complexity is **O(n)**.

We are also storing startIndex and endIndex in every call, so Space Complexity is 2n or **O(n)**.