Mastering Recursion For Beginners [Part 3]
This is part 3 of a series of articles on mastering recursion for beginners. In this article, we’ll look at how to write a recursive function that checks if a given string is a palindrome.
Q3. Given a string, write a recursive function that checks if the given string is a palindrome, else, not a palindrome.
What is Palindrome?
Palindrome :- a word, phrase, or sequence that reads the same backwards as forwards, e.g. madam or nurses run.
Before defining the function, we need to decide what states are needed. We will need the string, a variable i pointing to the first character initially, and a variable j pointing to the last character.
The function PalindromicString(string s, int i, int j) determines whether the sub-string of s starting at index i and ending at index j is a palindrome.
In order to use recursion to determine whether a given string is a palindrome, we first need to find the transition for our first step. This involves comparing the first and last characters of the string. If they are equal, then we can let the recursion do the remaining work. The transition condition is defined as follows: PalindromicString(s,i,j) = PalindromicString(s,i+1,j-1) if s[i] = s[j], otherwise false.
Basically by leap of faith we are saying “hey recursion tell me if string starting from index i+1 and ending with index j-1 is palindrome or not.” Just trust that it will give you the right answer. So if true is returned, you need to check the current indexes i and j. If they are equal, let’s say that they are palindromes. If not, we return false. This completes the state transitions.
In the base case, when i equals j, the substring s[i:j] has a length of 1, which makes it a palindrome. This is because a string of length 1 can be read the same forwards and backwards. Therefore, we can return true in this case. For an even-length string, if i plus 1 equals j (min length =2), need to check for s[i]==s[j]
Hope this problem serves you well and helps you understand concept of recursion easily.
