Thread: 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)

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)

If you want it to be general, change it to this:

if(start >= end)