# Recursive exercises.

• 10-16-2011, 09:57 PM
danthegreat
Recursive exercises.
I'm having a problem with this recursive function

I can't seem to grasp the thought process for recursion. It's difficult for me and gives me a headache. It's not how do it, its just how i dont know when it will stop...

the function below needs to return true if the parameter is a palindrome. What's wrong with the code? The output is wrong but in my head it seems correct..I've tried outputting serveral variables and nothing really leads me to source of the problem.

Code:

```    public static boolean isPalindrome(String phrase)     {         int length=phrase.length();         String reverse="";                 if(length>0)         {                         reverse+=phrase.charAt(length-1);             System.out.print(reverse);             isPalindrome(phrase.substring(0, length-1));                     }         if(phrase.equals(reverse))         {             return true;         }         else         {             return false;         } }```
phrase currently = racecar

output is

racecarfalse

it should be racecartrue

something with that if statement. Is this a problem with recursion? Is the true being replaced with falses?
Any suggestions?
• 10-16-2011, 10:20 PM
sunde887
Re: Recursive exercises.
You have good logic but you are making a mistake. The reverse string is local to the method, meaning a new one is created each time a recursive call is made. Try changing the System.out.print(...) to a System.out.println(...) to highlight the problem more. You can keep reverse variable but it has to be declared elsewhere. Or you can probably change the logic to not need a string variable.
• 10-16-2011, 10:35 PM
danthegreat
Re: Recursive exercises.
My teacher says we are not allowed to change the parameters. How do I "change" my logic to not require the use of a reverse...I've tried replacing it with a boolean, a counter, but all of those are variables so they all get replaced...
• 10-16-2011, 10:39 PM
sunde887
Re: Recursive exercises.
You can't change the parameter, but reverse is not a parameter, it is a locally declared and initialized string. The logic change method would require some extra thinking, given a word with 7 letters that IS a palindrome what is true about the first letter and the last letter? How about the second letter and the second to last letter? Repeat this logic recursively.

If you do not want to rethink the logic, what you have will work, you will just need to change where the variable reverse is declared and initialized (move it outside the method).
• 10-16-2011, 10:48 PM
danthegreat
Re: Recursive exercises.
I thought of this. However, it only checks correctly Length-1 and (Length+1)-(Length). Therefore, it won't check position 0, (Length-Length)...That's the only problem.

Code:

```public static boolean isPalindrome(String phrase)        {                 int length=phrase.length();                                                 if(length>0)                 {                                         if(phrase.charAt(length-1)==phrase.charAt((length+1)-length))                         {                                        isPalindrome(phrase.substring(0, length-1));                         }                         else                         {                                 return false;                         }                                                                                                                 }                 return true;                 }```
• 10-16-2011, 10:51 PM
sunde887
Re: Recursive exercises.
Why not simply check charAt(0) to charAt(length-1), and with each recursive call shrink the string on both sides.
• 10-16-2011, 11:24 PM
danthegreat
Re: Recursive exercises.
Code:

```public static boolean isPalindrome(String phrase)        {                 int length=phrase.length();                                                 if(length>0)                 {                                         if(phrase.charAt(0)==phrase.charAt(length-1))                         {                                        isPalindrome(phrase.substring(XXXXX), length-1));                         }                         else                         {                                 return false;                         }                                                                                                                 }                 return true;                 }```
Where X is placed, its unclear to me how to solve this. Cutting the string on the beginning would require to write (length+1)-(length). however, this will not check position 0. How would you be able to fufill both requests
• 10-16-2011, 11:39 PM
gcalvin
Re: Recursive exercises.
1. If the length of the String is 1 or less (1, not 0), it is a palindrome. Return true. (This solves "I don't know when it will stop.")
2. If the first character is not the same as the last character, it is not a palindrome. Return false. Otherwise...
3. If the part between the first and last characters is a palindrome, it is a palindrome. If it's not, it's not.
• 10-17-2011, 12:34 AM
sunde887
Re: Recursive exercises.
The XXXX can be simply 1, you check the 0 character to get into that condition so it has been checked already. Also, see gcalvins points.
• 10-17-2011, 01:08 AM
danthegreat
Re: Recursive exercises.
I get an error:
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.substring(String.java:1937)
at howard_recursiveExercises.isPalindrome(recursiveEx ercises.java:175)
at howard_recursiveExercises.isPalindrome(recursiveEx ercises.java:175)
at howard_recursiveExercises.isPalindrome(recursiveEx ercises.java:175)
at howard_recursiveExercises.isPalindrome(recursiveEx ercises.java:175)
at howard_recursiveExercises.main(_recursiveExercises .java:12)
• 10-17-2011, 01:42 AM
danthegreat
Re: Recursive exercises.
nvm figured it out, its if length>1 sigh...
lol still don't understand how or why but....it works!