As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/

Recursive functions

CarpyCarpy Registered User regular
edited September 2012 in Help / Advice Forum
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

  • musanmanmusanman 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

    sic2sig.jpg
  • SevorakSevorak 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".

    steam_sig.png 3DS: 0748-2282-4229
  • CarpyCarpy 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.

Sign In or Register to comment.