Homework SourseProgramming Assignment 7 Recursion This assignment is to wri
Programming Assignment #7
(Recursion)
This assignment is to write some methods that perform simple array operations recursively.
For this assignment you will write the bodies for 3 recursive methods of the ArrayRecursion class, available on the class web page in file ArrayRecursionTest.java
You are to make NO other changes to the ArrayRecursion class other than writing the 3 method bodies. Also make no changes to the test class.
Note that the public methods of ArrayRecursion – reverse(), sort(), and getIndexOfLargest() – cannot be recursive because they have no parameters. Each of these methods calls a private recursive “helper” method that does the work recursively. You will write the bodies of these recursive helper methods.
Remember that recursion is not merely another way to implement a loop. Recursive algorithms always have one or more “base” or “trivial” cases that are solved nonrecursively, and each recursive call must be made for a “reduced case” of the problem that gets closer to the trivial case. Therefore, to receive credit you must implement the algorithms given below.
reverseRecurse - reverse the order of the values stored in the array, using this algorithm:
Swap the first element value with the last. Then, recursively reverse that portion of the array containing all but the first and last elements
recursiveGetIndexOfLargest - return the index of the largest value stored in the array, using this algorithm:
Find the largest value in that portion of the array containing all but the last element. Compare that value to the value in the last element and return the index of the larger of the two.
recursiveSort – sort the array in ascending order, using the selection sort algorithm and the recursiveGetIndexOfLargest method you wrote in 2.
Find the largest value in the array and swap it with the last element. Then, remove the last element and repeat the process for the shortened array.
Due Date: Thursday, December 1st
Because this is the last day of class, late assignments cannot be accepted
What to Upload and Hand In
Hand in printouts of ArrayRecursionTest.java and the program output in class
Upload a zip file of your Netbeans project folder
CODE:
Solution
File name: ArrayRecursionTest.java
public class ArrayRecursionTest
{
public static void main(String[] args)
{
ArrayRecursion list = new ArrayRecursion() ;
System.out.println(\"\ Original array: \" + list) ;
list.reverse() ;
System.out.println(\"\ Reversed array: \" + list);
System.out.println(\"Index of the Largest Value in the array: \" +
list.getIndexOfLargest()) ;
list.sort() ;
System.out.println(\"\ Sorted array: \" + list) ;
}
}
File name: ArrayRecursion.java
import java.util.Random;
class ArrayRecursion
{
// Declare the variables
private int [] list ;
private int count ;
private Random r ;
/* Create the array Recursion to create the elements in ` random order*/
public ArrayRecursion()
{
r = new Random() ;
count = r.nextInt(6) + 10 ;
list = new int[count] ;
//Execute the for loop
for (int i = 0 ; i < count ; i++)
list[i] = r.nextInt(90) + 10 ;
}
// Return the list as a string
public String toString()
{
String out = \"\" ;
for (int i = 0 ; i < count ; i++)
out += list[i] + \" \" ;
return out + \"\ \" ;
}
// Reverse the order of values stored in list
public void reverse()
{
//Call the reverseRecurse()
reverseRecurse(list, 0, count) ;
}
// define the reverseRecurse() method
private void reverseRecurse ( int[] list, int start, int count )
{
// if the array has only one element
if(count - 1 == start || count == start)
{
//Return to address on top of stack
return ;
}
// otherwise, swap the elements
int temp = list[start] ;
list[start] = list[count - 1] ;
list[count - 1] = temp ;
reverseRecurse(list, ++start, --count) ;
}
/* Method to return the index of the largest value in the array.*/
public int getIndexOfLargest()
{
return recursiveGetIndexOfLargest(list, count) ;
}
/* Define the method to return the index of the largest value in the array.*/
private int recursiveGetIndexOfLargest( int[] list, int
count )
{
// if the array has only one element
if(count == 1)
//Return element
return 0 ;
// Assign the index of the element
int index = recursiveGetIndexOfLargest(list, count
- 1) ;
if(list[index] > list[count - 1])
return index ;
else
return count - 1 ;
}
/* Sort the array in ascending order using the selection sort*/
public void sort()
{
recursiveSort(list, count) ;
}
//Define the method to sort the array
private void recursiveSort( int[] list, int count )
{
if(count == 1)
return ;
int last = list[count - 1] ;
int largest = recursiveGetIndexOfLargest(list,
count - 1) ;
if(last < list[largest])
{
list[count - 1] = list[largest] ;
list[largest] = last ;
}
recursiveSort(list, count - 1) ;
}
}
Sample Output:
Original: 94 82 93 78 38 51 97 98 64 96 54
Reversed: 54 96 64 98 97 51 38 78 93 82 94
Index of the Largest Value: 3
Sorted: 38 51 54 64 78 82 93 94 96 97 98
