Question

Programming Assignment #7

(Recursion)

This assignment is to write some methods that perform simple array operations recursively.

Specifically, you will write the bodies for the recursive methods of the ArrayRecursion class, available on the class web page.

No credit will be given if any changes are made to ArrayRecursion.java, other than completing the method bodies

Note that the public methods of ArrayRecursion – contains(), getIndexOfSmallest(), and sort() – 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.

To receive credit for a method, you must implement the algorithms given below

No credit will be given for any method that uses a loop. Loops are not necessary and if you use one you are missing the point of the assignment

1. recursiveGetIndexOfSmallest - return the index of the smallest value in the array, using this algorithm:

Find the smallest 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 smaller of the two.

2. recursiveSort – sort the array in descending order, using the selection sort algorithm and the recursiveGetIndexOfSmallest method you wrote in 1.

Find the smallest value in the array and swap it with the last element. Then, repeat the process for that portion of the array containing all but the last element.

3. recursiveContains – return a boolean indicating whether a given int is on the list

See any of our recursion examples using arrays for hints

Due Date: Thursday, December 5th

CODE:

/*  File: ArrayRecursion.java
 *
 *  Programmer: your name
 *
 */

import java.util.Random;
import javax.swing.JOptionPane;

/**
 * A class that performs some simple array operations recursively
 * @author Greg
 */
public class ArrayRecursion
{
   // instance var's
   private int[] list ;       // array of ints
   private int size ;         // number of elements

   /**
    * Create an ArrayRecursion object. 
    * Creates an array with between 10 and 15 elements, and fills it with
    * random positive 2-digit ints
    */
   public ArrayRecursion()
   {
      Random r = new Random();
      size = r.nextInt(6) + 10;
      list = new int[size];

      for (int i = 0; i < size; i++)
      {
         list[i] = r.nextInt(90) + 10;
      }
   }

   /**
    * Return the list as a string
    * @return a string containing all ints stored in list
    */
   public String toString()
   {
      String out = "";
      for (int i = 0; i < size; i++)
      {
         out += list[i] + "  ";
      }
      return out + "\n";
   }

   /**
    * Returns the index of the smallest value in the array.
    * @return the index of the smallest value in the array
    */
   public int getIndexOfSmallest()
   {
      return recursiveGetIndexOfSmallest(list, size);
   }

   // recursive "helper" method to return index of smallest value
   // called by public method getIndexOfSmallest()
   private int recursiveGetIndexOfSmallest(int[] list, int count)
   {
      return -999;   // bogus value to enable program skeleton to run
   }

   /**
    * Sort the array in descending order using the selection sort
    */
   public void sort()
   {
      recursiveSort(list, size);
   }

   // recursive "helper" method to sort the array
   // called by public method sort()
   private void recursiveSort(int[] list, int count)
   {
   }
   
   /**
    * Indicates whether a given int is on the list
    * @param target the int to search for
    * @return true if target is on the list, false if not
    */
   public boolean contains (int target)
   {
      return recursiveContains(list,size,target) ;
   }
   
   // recursive "helper" method to search the array
   // called by public method contains()
   private boolean recursiveContains(int[] list, int count, int target)
   {
     return false ;   // bogus return value to enable program skeleton to run
   }   
   
   public static void main(String[] args)
   {
      ArrayRecursion list = new ArrayRecursion();

      System.out.println("\nOriginal:  " + list);

      System.out.println("Smallest value is at index: "
              + list.getIndexOfSmallest());
      list.sort();
      System.out.println("\nSorted:    " + list);
     
      String target = JOptionPane.showInputDialog("Number to search for?") ;
      int searchee = Integer.parseInt(target) ;
      
      if (list.contains(searchee))
         System.out.println(searchee + " is on the list");
      else
         System.out.println(searchee + " is not on the list");
   }
}

Answer 1

SOURCE CODE IN JAVA:

/* File: ArrayRecursion.java

*

* Programmer: your name

*

*/

import java.util.Random;

import javax.swing.JOptionPane;

/**

* A class that performs some simple array operations recursively

* @author Greg

*/

public class ArrayRecursion

{

// instance var's

private int[] list ; // array of ints

private int size ; // number of elements

/**

* Create an ArrayRecursion object.

* Creates an array with between 10 and 15 elements, and fills it with

* random positive 2-digit ints

*/

public ArrayRecursion()

{

Random r = new Random();

size = r.nextInt(6) + 10;

list = new int[size];

for (int i = 0; i < size; i++)

{

list[i] = r.nextInt(90) + 10;

}

}

/**

* Return the list as a string

* @return a string containing all ints stored in list

*/

public String toString()

{

String out = "";

for (int i = 0; i < size; i++)

{

out += list[i] + " ";

}

return out + "\n";

}

/**

* Returns the index of the smallest value in the array.

* @return the index of the smallest value in the array

*/

public int getIndexOfSmallest()

{

return recursiveGetIndexOfSmallest(list,size);

}

// recursive "helper" method to return index of smallest value

// called by public method getIndexOfSmallest()

private int recursiveGetIndexOfSmallest(int[] list, int count)

{

if(count==1)

return 0;

else

{

int min=recursiveGetIndexOfSmallest(list,count-1);

if(list[count-1]<list[min])

return count-1;

else

return min;

}

}

/**

* Sort the array in descending order using the selection sort

*/

public void sort()

{

recursiveSort(list, size);

}

// recursive "helper" method to sort the array

// called by public method sort()

private void recursiveSort(int[] list, int count)

{

if(count>1)

{

int min=recursiveGetIndexOfSmallest(list,count);

int temp=list[count-1];

list[count-1]=list[min];

list[min]=temp;

recursiveSort(list,count-1);

}

}

/**

* Indicates whether a given int is on the list

* @param target the int to search for

* @return true if target is on the list, false if not

*/

public boolean contains (int target)

{

return recursiveContains(list,size,target) ;

}

// recursive "helper" method to search the array

// called by public method contains()

private boolean recursiveContains(int[] list, int count, int target)

{

if(count==0)

return false;

else

{

if(list[count-1]==target)

return true;

else

return recursiveContains(list,count-1,target);

}

}

public static void main(String[] args)

{

ArrayRecursion list = new ArrayRecursion();

System.out.println("\nOriginal: " + list);

System.out.println("Smallest value is at index: "

+ list.getIndexOfSmallest());

list.sort();

System.out.println("\nSorted: " + list);

String target = JOptionPane.showInputDialog("Number to search for?") ;

int searchee = Integer.parseInt(target) ;

if (list.contains(searchee))

System.out.println(searchee + " is on the list");

else

System.out.println(searchee + " is not on the list");

}

}

OUTPUT:

33 92 89 34 54 27 29 Original: 87 65 40 23 26 26 Smallest value is at index: 3 Sorted: 92 89 87 6554_40 34 33 29 27 26 26 23