How does the recursive Palindrome function work?

Question

I am working on some introductory recursion problems, and I have a clarifying question that I would like to get an answer to. The most egregious question I have is how does this recursion work in solving the problem below?

Despite the fact that I solved the problem, I just don’t understand how the recursion call gets inside the string. It would seem that just by looking at the code, this method will only check two characters at both ends of a given string without checking the rest. My tutorial gives a very unsatisfactory answer, basically don't worry about how recursion works while your return statement fixes the problem. But it’s hard for me to understand how to approach the subsequent problems of recursion without understanding how to trace a recursive method in the same way as you could trace a loop.

Any words of wisdom will be greatly appreciated.

Thanks!

public class isPalindrome { public static boolean isPalindrome(String str) { //test for end of recursion if(str.length() < 2) {return true;} //check first and last character for equality if(str.charAt(0) != str.charAt(str.length() - 1)){return false;} //recursion call return isPalindrome(str.substring(1, str.length() - 1)); } public static void main(String[] args) { System.out.print(isPalindrome("deed")); } } 

Answer 1

The isPalindrome () function is recursively called on str.substring (1, str.length () -1). Thus, a callstack will look like this for calls to isPalindrome ():

 1. isPalindrome("abcddcba"): ("a" == "a") = true, so recurse 2. isPalindrome("bcddcb"): ("b" == "b") = true, so recurse 3. isPalindrome("cddc"): ("c" == "c") = true, so recurse 4. isPalindrome("dd"): ("d" == "d") = true, so recurse 6. isPalindrome(""): length < 2, so return true 

The return value of the last call will propagate to the very top.

With recursion, pictures always help. Do your best to display the column as a chart. This will allow you to visualize and therefore better understand more complex recursions. This is a simple "linear" recursion, but you will end up with a "tree" like recursion.

Here is an image that illustrates this exact problem for you to better visualize:

Answer 2

Think of a palindrome:

 risetovotesir 

This can be created starting with the palindrome v (a single-character string is always a palindrome, like an empty string) and adds the same letter to the beginning and back:

  v Start with palindrome 'v'. ovo Add 'o' to both ends. tovot Then 't'. etovote Then 'e'. setovotes Then 's'. isetovotesi Then 'i'. risetovotesir And finally 'r'. 

The process used by this recursive function is in the opposite direction, breaking the bit in half. It determines if this is a palindrome, if both:

• the first and last characters are equal; and
• the inside of the line (after removing these two) is the palindrome.

Therefore, the code can be written as:

 public static boolean isPalindrome (String str) { // Zero- or one-character string is a palindrome. if (str.length() < 2) return true; // If first and last characters are different, it NOT palindromic. if (str.charAt (0) != str.charAt (str.length() - 1)) return false; // Otherwise it palindromic only if the inner string is palindromic. return isPalindrome (str.substring (1, str.length () - 1)); } 

Using the peed deep line, different levels:

 1. length 9 >= 2, both ends are 'p', next level checks 'eed dee'. 2. length 7 >= 2, both ends are 'e', next level checks 'ed de'. 3. length 5 >= 2, both ends are 'e', next level checks 'd d'. 4. length 3 >= 2, both ends are 'd', next level checks ' ' (space). 5. length 1 < 2, return true. 

Alternatively, the non-palindrome (albeit painfully close) star rots gives you:

 1. length 9 >= 2, both ends are 's', next level checks 'tar rot'. 2. length 7 >= 2, both ends are 't', next level checks 'ar ro'. 3. length 5 >= 2, ends are 'a' and 'o', so return false.