How does recursive isPalindrome function work?

Question

I'm working on some introductory recursion problems and I have a clarifying question I'd like to get answered. The most nagging question I have is how is this recursion operating in the solved problem below?

Despite having solved the problem, I'm just not understanding how the recursion call makes its way into the interior of the string. It would seem, from just looking at the code, that this method would only ever check the two characters on either end of the given string, without checking the rest. My textbook gives the deeply unsatisfying answer of, basically, don't worry about how recursion works as long as your return statement refines the problem. But I'm having difficulty knowing how to approach subsequent recursion problems without understanding how one can trace a recursive method in the same way one would trace a loop.

Any words of wisdom would be much 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"));
}
}

Solution 1

The isPalindrome() function is recursively being called on str.substring(1, str.length() -1). So the callstack would look like this for the isPalindrome() calls:

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 all the way to the top.

With recursion, pictures always help. Do your best to draw out the callstack as a diagram. It'll allow you to visualize, and therefore better understand, more complex recursions. This is a simple "linear" recursion but you'll eventually face "tree" like recursions.

Here's a picture that illustrates this exact problem for you to better visualize:

Solution 2

Think of the palindrome:

risetovotesir

This can actually be built by starting with the palindrome v (a one-character string is always a palindrome, as is an empty string) and adding the same letter to front 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 that recursive function is in the opposite direction, breaking the string down bit by bit. It detects if it is indeed a palindrome is if both:

• the first and last characters are equal; and
• the inside of the string (once those two are removed) is a palindrome.

Hence 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's NOT palindromic.

    if (str.charAt (0) != str.charAt (str.length() - 1))
        return false;

    // Otherwise it's palindromic only if the inner string is palindromic.

    return isPalindrome (str.substring (1, str.length () - 1));
}

Using a string of peed deep, the different levels are:

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, a non-palindrome (although tantalisingly close) of 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.

Comments

[gryb]

Thanks the diagram was quite helpful, I think I beginning to grasp the concept.

[Nadir Muzaffar]

no worries, once you grab the concept, it'll become easier to understand other recursive algorithms =D