# Recursive functions

Registered User regular
edited September 2012
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.

Carpy on

## Posts

• Registered User regular
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

• Registered User regular
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".

3DS: 0748-2282-4229
• Registered User regular
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.