Results 1 to 11 of 11
  1. #1
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default 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.

    Java 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?
    Last edited by danthegreat; 10-16-2011 at 10:59 PM.

  2. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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.

  3. #3
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default 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...

  4. #4
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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).

  5. #5
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default 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.

    Java 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;
    		
    
    
    
    
    
    
    }

  6. #6
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default Re: Recursive exercises.

    Why not simply check charAt(0) to charAt(length-1), and with each recursive call shrink the string on both sides.

  7. #7
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default Re: Recursive exercises.

    Java 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

  8. #8
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    952
    Rep Power
    5

    Default 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.

  9. #9
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #10
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default 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)

  11. #11
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default Re: Recursive exercises.

    nvm figured it out, its if length>1 sigh...
    lol still don't understand how or why but....it works!

Similar Threads

  1. need some exercises
    By JohnPringle83 in forum New To Java
    Replies: 10
    Last Post: 05-11-2011, 08:48 PM
  2. OOP exercises
    By sunde887 in forum New To Java
    Replies: 6
    Last Post: 01-09-2011, 09:05 PM
  3. Exercises
    By amzers in forum New To Java
    Replies: 6
    Last Post: 12-12-2010, 10:58 AM
  4. Some exercises
    By javaamateur in forum New To Java
    Replies: 7
    Last Post: 12-02-2009, 01:00 AM
  5. Exercises
    By lclclc in forum New To Java
    Replies: 3
    Last Post: 09-14-2009, 11:20 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •