Recursive functions

Carpy

In my algorithms class I was recently given an assignment to write a recursive function to determine if a given string is a palindrome. My solution works, but i'm not sure why it does.

public static boolean isPalindrome(String str)
    {
        if (str.length() == 1)
            return true;
        else if (str.length() == 2 && str.charAt(0) == str.charAt(1))
        {
                return true;
        }
        else if( str.charAt(0) == str.charAt(str.length()-1))
            return isPalindrome(str.substring(1,str.length()-1));
        else
            return false;
    }

Based on my understanding of the substring() method this shouldn't ever change the last character of the string. But if i change it to .substring(1,str.length()-2) it doesn't correctly identify palindromes.

musanman

charAt() calls 0 to str.length() - 1 since it starts reference at 0, str.length actually counts all the characters and so it starts at 1

example: "test"
charAt() can call 0 to 3, but length = 4

Sevorak

The beginIndex of the substring method is inclusive, but the endIndex is exclusive. Meaning the resulting substring will be the characters from beginIndex to endIndex - 1. For example:

RACECAR
0123456

The first iteration of isPalidrome("RACECAR") will see that the first and last characters are the same, then will call itself on str.substring(1, 6) since the length of the string is 7.

Since the endIndex of substring is exclusive, the actual indices used are 1-5, giving you the substring "ACECA".

Carpy

Ahh that makes a lot of sense. I had a hunch that is was something along those lines but the String API online doesn't mention that. Thank you very much.