# Problems with recursion

• September 19th, 2009, 11:00 PM
KingLane
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:

Code :

```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 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)
• September 20th, 2009, 02:53 AM
KingLane
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.

Code :

```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)
• September 20th, 2009, 07:19 PM
KingLane
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:

Code :

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

Code :

`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.
• September 20th, 2009, 09:04 PM
helloworld922
Re: Problems with recursion
If you want it to be general, change it to this:
Code :

`if(start >= end)`
• September 20th, 2009, 11:02 PM
KingLane
Re: Problems with recursion
Yes, you're right, helloworld922. I've made the changes. Thank you for your response.