Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Problems with recursion

  1. #1
    Junior Member
    Join Date
    Sep 2009
    Posts
    8
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Problems with recursion

    Hey guys,

    I am currently enrolled in a CS2 class and am working on a problem involving recursion. The problem is similar to checking that a string is a palindrome, but it's a little different. In this program, A's pair with T's and C's pair with G's. Given an expression, such as ACGCGT, the program must check that each character has an appropriate corresponding character. So the first character is an A and the last character is a T, the second character is a C and the second to last character is a G, and so on. The above expression meets these conditions. For this assignment, the expression will contain an even number of characters.

    The code I have so far:

    import java.util.Scanner;
     
    public class bioPalindrome {
     
    	public static void main(String[] args) {
     
    		Scanner console = new Scanner(System.in);
     
    		System.out.println("Please enter the DNA string to be examined."); // prompting user for the dna string.
    		String dnaString = console.nextLine(); // storing the input in to the variable dnaString
    		dnaString = dnaString.toUpperCase(); // converting the characters to upper case.
    		int stringLength = dnaString.length(); // storing the length of the string into the variable stringLength.
    		System.out.println(dnaString + " " + stringLength); // to check that the variables are being properly initialized...remove later.
     
    		boolean isPalindrome = checkPalindrome(dnaString, 0, stringLength - 1); // calling the method, checkPalindrome, where 0 is the position of the first character of the string and stringLength - 1 is the  last character of the string.
    		System.out.println(isPalindrome);
     
    	}
     
    	//-----------------------------------------------------------------------------------------------------------------------------------
    	// User defined recursive method to check that the input is a biopalindrome.
     
    	public static boolean checkPalindrome(String stringIn, int start, int end) {
    		if(stringIn.length() == 0) // base case
    			return true;
    		else if(stringIn.charAt(start) == 'A' && stringIn.charAt(end) == 'T' || stringIn.charAt(start) == 'T' && stringIn.charAt(end) == 'A' || stringIn.charAt(start) == 'C' && stringIn.charAt(end) == 'G' || stringIn.charAt(start) == 'G' && stringIn.charAt(end) == 'C') { // general case
    			start++;
    			end--;
    			return checkPalindrome(stringIn, start, end);
    		} else
    			return false;
    	}
    }

    This compiles, but when I try to run the program with an expression like, AATT, I get this message: Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 4
    at java.lang.String.charAt(String.java:558)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:3 5)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:3 8)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:3 8)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:3 8)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:3 8)
    at bioPalindrome.main(bioPalindrome.java:24)

    I think what I need to do is use the substring method, but this introduces problems in the parameter list of the method. For example, instead of passing a string, and two int values, when calling the method, I tried to pass checkPalindrome(dnaString.substring(0, stringLength - 1)), but it won't allow this in the user - defined method where the parameter list will be public static boolean checkPalindrome(String stringIn.substring(int a, int b)). I get a "multiple markers at this line error".

    I appreciate your help. Thanks.

    I am using Eclipse Version 3.5.0
    Mac OS X version 10.5.8
    Java version Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0.20)
    Last edited by KingLane; September 20th, 2009 at 07:21 PM.


  2. #2
    Junior Member
    Join Date
    Sep 2009
    Posts
    8
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Problems with recursion

    I made some corrections to the code and have posted the new code below. The program runs correctly if I input a string that does not contain any A's, T's, C's or G's, but still does not run properly if I input something correct such as "AATT" (without the quotes). I think the problem is somewhere in the second conditional of the user-defined method, checkPalindrome.

    import java.util.Scanner;
     
    public class bioPalindrome {
     
    	public static void main(String[] args) {
     
    		Scanner console = new Scanner(System.in);
     
    		System.out.println("Please enter the DNA string to be examined."); // prompting user for the dna string.
    		String dnaString = console.nextLine(); // storing the input in to the variable dnaString
    		dnaString = dnaString.toUpperCase(); // converting the characters to upper case.
    		System.out.println(dnaString + " " + dnaString.length()); // to check that the variables are being properly initialized...remove later.
     
     
    		boolean isPalindrome = checkPalindrome(dnaString, 0, dnaString.length()); // calling the method, checkPalindrome, where 0 is the position of the first character of the string and stringLength is the  last character of the string.
     
    		if(isPalindrome == true)
    			System.out.println("The DNA string entered is a biopalindrome.");
    		else 
    			System.out.println("The DNA string entered is not a biopalindrome.");
     
    	}
     
    	//-----------------------------------------------------------------------------------------------------------------------------------
    	// User defined recursive method to check that the input is a biopalindrome.
     
    	public static boolean checkPalindrome(String stringIn, int start, int end) {
     
    		if(stringIn.length() - 1 == 0) // base case
    			return true;
    		else if(stringIn.charAt(start) == 'A' && stringIn.charAt(end - 1) == 'T' || stringIn.charAt(start) == 'T' && stringIn.charAt(end - 1) == 'A' || stringIn.charAt(start) == 'C' && stringIn.charAt(end - 1) == 'G' || stringIn.charAt(start) == 'G' && stringIn.charAt(end - 1) == 'C') { // general case
    			start++;
    			end--;
    			return checkPalindrome(stringIn, start, end);
    		} else
    			return false;
    	}
    }

    If I input "AATT", I receive the following error when running the program: Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 4
    at java.lang.String.charAt(String.java:558)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:4 0)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:4 3)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:4 3)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:4 3)
    at bioPalindrome.checkPalindrome(bioPalindrome.java:4 3)
    at bioPalindrome.main(bioPalindrome.java:24)
    Last edited by KingLane; September 20th, 2009 at 07:22 PM.

  3. #3
    Junior Member
    Join Date
    Sep 2009
    Posts
    8
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: The code seems to work now

    I made a small change and the code seems to work now. The change I made is found within the first conditional statement of the checkPalindrome user-defined method. The code did read:

    if(stringIn.length() - 1 <= 0 && start == end)


    and now the code reads


    if(/*stringIn.length() - 1 <= 0 &&*/ start == end)


    I just commented out the string.length() - 1. The program works with the given string that we are to examine with the program. I'm not sure if it'll work for all odd-numbered strings. I'll post back if I find that the code is not general enough.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,895
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Problems with recursion

    If you want it to be general, change it to this:
    if(start >= end)

  5. The Following User Says Thank You to helloworld922 For This Useful Post:

    KingLane (September 20th, 2009)

  6. #5
    Junior Member
    Join Date
    Sep 2009
    Posts
    8
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Problems with recursion

    Yes, you're right, helloworld922. I've made the changes. Thank you for your response.

Similar Threads

  1. Replies: 4
    Last Post: September 19th, 2009, 11:56 PM
  2. If you have any .NET problems
    By antony_t in forum The Cafe
    Replies: 1
    Last Post: August 26th, 2009, 10:49 AM
  3. big problems bounding() in Java2d with LineBreakMeasurer.
    By fenderman in forum AWT / Java Swing
    Replies: 0
    Last Post: July 27th, 2009, 01:15 PM
  4. Problems in setting classpath
    By missyati in forum Java Theory & Questions
    Replies: 3
    Last Post: June 30th, 2009, 12:43 AM
  5. Replies: 1
    Last Post: April 1st, 2009, 02:47 PM

Tags for this Thread