*Needed Files*

EndlessExample.java :

// From stackoverflow web site with modifications

public class EndlessExample {

static int counter = 0;

public static void endless() throws StackOverflowError

{

counter++;

endless();

}

public static void main(String args[]) {

try {

endless();

} catch(StackOverflowError t) {

// more general: catch(Error t)

// anything: catch(Throwable t)

System.out.println("Caught "+t);

// t.printStackTrace();

}

System.out.println("After the error...counter = " + counter);

}

}

ProgChal_1_Partial.java :

// Asg-5 PC-1 Recursive multiplication

// Use long values for larger ints

import java.util.Scanner;

public class ProgChal_1_Partial

{

public static void main(String[] args)

{

long val1, val2;

Scanner keyboard = new Scanner(System.in);

System.out.print("Enter an integer value: ");

val1 = keyboard.nextLong();

System.out.println("val1 = " + val1);

System.out.print("Enter another integer value: ");

val2 = keyboard.nextLong();

System.out.println("val2 = " + val2);

System.out.println(val1 + " times " + val2 + " = "

+ multiplyByAdding(val1, val2));

}

public static long multiplyByAdding(long x, long y) throws StackOverflowError

{

// You complete the code here. It is very short but is recursive

}

}

RecursionDemo.java :

/** This class demonstrates the Recursive.message method. */

public class RecursionDemo { public static void main(String[] args) { Recursive.message(5); } }

Recursive.java :

/** This class has a recursive method, message, which displays a message n times. */

public class Recursive { public static void message(int n) { if (n > 0) { System.out.println("This is a recursive method where n = "+ n); message(n -1); } } }

A demo program on recursion from our textbook is posted in RecursionDemo folder. It has been modified to make the output more meaningful by displaying the value of the recursion control variable, n, each time the recursive method is called. Typically, recursive methods are quite simple,

Recursive methods move toward completion by repeatedly calling themselves with a simpler version of the original problem. They need a way to control the number of times they call themselves. In the Recursion demo mentioned above the variable n decreases with each call until it reaches zero. This indicates that the recursion is finished, and the method ends.

Most of the exercises and programming challenges can be done quite simply by regular for loop methods but not all. Recursive methods will be used (and needed) extensively in your Data Structures course, next semester so learning them now will be an advantage.

Part-A

Programming Challenge 2 (isMember Method) page1066:

Write a recursive Boolean method named isMember. The method should search an array for a specified value, and return true if the value is found in the array, or false if the value is not found in the array.

Note carefully: Your solution must not be a standard linear search of the array. It must be a recursive search.

You are given a main() that sets up the problem and calls the isMember() method. Your output should match the sample output shown following the main program below:

public static void main(String[] args)

{

// Make an array.

final int ARRAY_SIZE = 10;

int[] numbers = {2, 4, 16, 20, 14, 12, 10, 6 ,18, 8 };

// Test all of the values from 0 through 20 and see if

// they are in the array.

for (int x = 0; x

{

if (isMember(numbers, x, ARRAY_SIZE))

System.out.println(x + " is found in the array.");

else

System.out.println(x + " is not found in the array.");

}

}

Part-B

Programming Challenge 5 (Palindrome Detector) page1067:

A palindrome is any word, phrase or sentence that reads the same forward as backward. Here is a simple main() that will call the recursive method isPalindrome() to determine if the phrase is a palindrome or not.

public static void main(String[] args) { // Create an array of strings to test. String[] testStrings = { "Able was I ere I saw Elba", "Four score and seven years ago", "Now is the time for all good men", "Desserts I stressed", "Ask not what your country can do for you", "A man a plan a canal Panama", "D", "", "Kayak"};

// Test the strings. for (int i = 0; i

Here is the output that results from running this main program and calling: isPalindrome(testStrings[i].toUpperCase()) for each of the strings.

You must prepare the method isPalindrome( ) as a recursive method to see if each string is a palindrome or not.

Part-C Here we consider Programming Challenge: 1. Recursive Multiplication. The solution is quite simple and it is useful for demonstrating what can unexpectedly go wrong with recursive solutions.

A partial solution is posted on our Omnivox dropbox as ProgChal_1.java.

This solution needs completion of the multiplyByAdding() method. Set this up as a Java program and complete the missing method.

Run your program. First enter the values: 123 and 321 when prompted for input. You should get the correct result as 39483.

Run it again and try the values: 12345 and 54321. You should now get the error: java.lang.StackOverflowError followed by repeated line number location (java.28 in our example) and no answer. This means that your program has run out of the stack memory. This memory was originally assigned when the program was loaded to run. This illustrates that Recursive solutions can unexpectedly run out of memory. Regular nonrecursive methods may require more complex programming and may take more time but, usually, do not simply run out of memory.

The program: EndlessExample.java is provided in the Dropbox entry for Asg-5. Set it up to run. When this program causes a StackOverflowError the catch block receives the error and displays a message about catching the error. It also displays a counter of how many times the endless method was called before the error occurred. A sample of this output window is shown below.

Repeat running EndlessExample a few more times to compare the values reported from the counter.

What to hand in:

Demonstrate to your teacher all of your work for Part-A, Part-B and Part-C.

Then submit your program listings in a Zip file.

C: Windowsls... 0 is not found in the array. 1 is not found in the array. 2 is found in the array. 3 is not found in the array. is found in the array 5 is not found in the array. 6 is found in the array. 7 is not found in the array. 8is found in the array. 9 is not found in the array. 10 is found in the array 11 is not found in the array. 12 is found in the array 13 is not found in the array. 14 is found in the array 15 is not found in the array. 16 is found in the array. 17 is not found in the array. 18 is found in the array 19 is not found in the array. 20 is found in the array Press any key to continue