Question

In this lab, you get to try your hand with some recursion operating on arrays and subarrays. All of the following methods of the class RecursionProblems must be fully recursive, with no loops allowed at all! (If-else statements are okay.) Because these methods are quite short, this last time there are six methods to write instead of the usual four. (The scoring rule is that you start gaining any points for this lab only at the third method that passes the tester.)

1.boolean allEqual(int[] arr, int start, int end) that checks if all elements in the subarray of arr from start to end, inclusive, are equal. Note that for the base case, all elements of an empty (that is, where start > end) or one-element subarray are equal by definition. After all, a subarray must by definition have at least two elements for it to have two different elements! (This principle generalizes to the counterintuitive but nonetheless true observation that any universal claim that you make about the members of an empty array is trivially true by definition.)

2.void arraycopy(double[] src, int start, double[] tgt, int start2, int len) that copies len elements from the location start of array src to the location start2 of array tgt. In other words, this method works exactly the same way as the method System.arraycopy. (But of course you are not allowed to call this existing method.) Hint: when len is less than one, do nothing. Otherwise copy the first element, and then recursively copy the remaining len - 1 elements.

3.boolean linearSearch(int[] arr, int x, int start, int end) that checks if the unsorted array arr contains the element x anywhere in the subarray from start and end, inclusive.

4.void reverse(int[] arr, int start, int end) that reverses the order of the elements in the subarray of arr from index start to end, inclusive. Note that this method does not create and return a new array, but modifies the contents of the parameter array arr in place by reassigning its elements.

5.public void parityPartition(int[] arr, int start, int end) that modifies the subarray of arr from start to end, inclusive, in place so that all odd numbers are first together in one bunch, followed by all even numbers in another bunch. The odd elements can end up in any order you want inside the first bunch, as do the even elements. For example, if your array a is currently [2, -1, 3, 4, 8, 5, -7], after the call parityPartition(a, 0, 6), the contents of this array might become [3, -1, -7, 5, 8, 4, 2]. (Hint: after testing for the base case of subarray that has only zero or one elements, the parities of the first and the last element of the subarray, whichever way they might be, will somehow allow you to continue the recursion with a smaller subarray.)

6.int countRuns(int[] arr, int start, int end) that counts how many runs (blocks of equal consecutive elements) there are in the subarray of arr from index start to index end, inclusive. For example, the array [4, 4, 4, -2, 0, -8, -8, 3, 3] has five runs, whereas the array [5, 5, 5, 5] has only one run. An empty subarray (that is, when start > end) has zero runs. (Hint: count how many elements are different from the next element.)

Answer 1

public class RecursionProblems {

   /**
   * Checks if all elements in the subarray of arr from start to end,
   * inclusive, are equal. Note that for the base case, all elements of an
   * empty (that is, where start > end) or one-element subarray are equal by
   * definition.
   *
   * @param arr
   *            - array
   * @param start
   *            - start index
   * @param end
   *            - end index
   */
   boolean allEqual(int[] arr, int start, int end) {
       // Check if array is empty
       if (start > end)
           return true;

       return (arr[start] == arr[end]) && allEqual(arr, start, end - 1);
   }

   /**
   * Copies len elements from the location start of array src to the location
   * start2 of array tgt. In other words, this method works exactly the same
   * way as the method System.arraycopy. (But of course you are not allowed to
   * call this existing method.) Hint: when len is less than one, do nothing.
   * Otherwise copy the first element, and then recursively copy the remaining
   * len - 1 elements.
   *
   * @param src
   *            - source array
   * @param start
   *            - start index in source array
   * @param tgt
   *            - target array
   * @param start2
   *            - start index of target array
   * @param len
   *            - number of elements to copy from source array
   */
   void arraycopy(double[] src, int start, double[] tgt, int start2, int len) {
       if (len < 1)
           return;

       // Copy element from source to target
       tgt[start2] = src[start];
       arraycopy(src, start + 1, tgt, start2 + 1, len - 1);
   }

   /**
   * Checks if the unsorted array arr contains the element x anywhere in the
   * subarray from start and end, inclusive.
   *
   * @param arr
   *            - array
   * @param x
   *            - search element
   * @param start
   *            - start index
   * @param end
   *            - end index
   */
   boolean linearSearch(int[] arr, int x, int start, int end) {
       if (start > end)
           return false;

       return ((arr[start] == x) || (arr[end] == x)) || linearSearch(arr, x, start + 1, end - 1);
   }

   /**
   * Reverses the order of the elements in the subarray of arr from index
   * start to end, inclusive. Note that this method does not create and return
   * a new array, but modifies the contents of the parameter array arr in
   * place by reassigning its elements.
   *
   * @param arr
   *            - Array
   * @param start
   *            - start index
   * @param end
   *            - end index
   */
   void reverse(int[] arr, int start, int end) {
       if (start > end)
           return;

       // Swap elements at start and end
       int temp = arr[start];
       arr[start] = arr[end];
       arr[end] = temp;
       reverse(arr, start + 1, end - 1);
   }

   /**
   * Shifts array elements one position down
   *
   * @param arr
   *            - Array
   * @param index
   *            - index
   */
   private void downShiftArray(int[] arr, int index) {
       if (index < 1)
           return;

       // Shift element
       arr[index] = arr[index - 1];
       downShiftArray(arr, index - 1);
   }

   /**
   * Modifies the subarray of arr from start to end, inclusive, in place so
   * that all odd numbers are first together in one bunch, followed by all
   * even numbers in another bunch. The odd elements can end up in any order
   * you want inside the first bunch, as do the even elements. For example, if
   * your array a is currently [2, -1, 3, 4, 8, 5, -7], after the call
   * parityPartition(a, 0, 6), the contents of this array might become [3, -1,
   * -7, 5, 8, 4, 2]. (Hint: after testing for the base case of subarray that
   * has only zero or one elements, the parities of the first and the last
   * element of the subarray, whichever way they might be, will somehow allow
   * you to continue the recursion with a smaller subarray.)
   *
   * @param arr
   *            - Array
   * @param start
   *            - start index
   * @param end
   *            - end index
   */
   public void parityPartition(int[] arr, int start, int end) {
       if (start > end)
           return;

       // Check if element at start and end is odd
       if ((arr[start] % 2) != 0) {
           int oddNum = arr[start];
           downShiftArray(arr, start);
           arr[0] = oddNum;
       }

       if ((arr[end] % 2) != 0)
           parityPartition(arr, start + 1, end);
       else
           parityPartition(arr, start + 1, end - 1);
   }

   /**
   * Counts how many runs (blocks of equal consecutive elements) there are in
   * the subarray of arr from index start to index end, inclusive. For
   * example, the array [4, 4, 4, -2, 0, -8, -8, 3, 3] has five runs, whereas
   * the array [5, 5, 5, 5] has only one run. An empty subarray (that is, when
   * start > end) has zero runs. (Hint: count how many elements are different
   * from the next element.)
   *
   * @param arr
   *            - Array
   * @param start
   *            - start index
   * @param end
   *            - end index
   */
   int countRuns(int[] arr, int start, int end) {
       if (start >= end)
           return 0;
      
       int count = 0;
       if (start == 0)
           count = 1;
          
       // Check if the next element is different
       if (arr[start] != arr[start + 1])
           count = 1;
      
       return count + countRuns(arr, start + 1, end);
   }

   /**
   * Displays the array
   */
   public static void printArray(int[] arr) {
       System.out.print("Array: ");
       if (arr.length >= 1) {
           System.out.print(arr[0]);

           for (int i = 1; i < arr.length; i++)
               System.out.print(", " + arr[i]);
       }
       System.out.println();
   }

   /**
   * Displays the array
   */
   public static void printArray(double[] arr) {
       System.out.print("Array: ");
       if (arr.length >= 1) {
           System.out.print(arr[0]);

           for (int i = 1; i < arr.length; i++)
               System.out.print(", " + arr[i]);
       }
       System.out.println();
   }

   public static void main(String[] args) {
       RecursionProblems r = new RecursionProblems();

       System.out.println("------------------------TEST allEqual------------------------");
       int[] emptyArr = {};
       printArray(emptyArr);
       System.out.println("allEqual: " + r.allEqual(emptyArr, 0, emptyArr.length - 1) + "\n");

       int[] oneEltArr = { 1 };
       printArray(oneEltArr);
       System.out.println("allEqual: " + r.allEqual(oneEltArr, 0, oneEltArr.length - 1) + "\n");

       int[] equalArr = { 1, 1, 1, 1, 1 };
       printArray(equalArr);
       System.out.println("allEqual: " + r.allEqual(equalArr, 0, equalArr.length - 1) + "\n");

       int[] unEqualArr = { 1, 1, 2, 1, 1 };
       printArray(unEqualArr);
       System.out.println("allEqual: " + r.allEqual(unEqualArr, 0, unEqualArr.length - 1) + "\n");

       System.out.println("------------------------TEST arraycopy------------------------");
       double[] source = { 1, 2, 3, 4, 5 };
       double[] target = { 11, 12, 13, 14, 15 };
       r.arraycopy(source, 1, target, 2, 3);
       System.out.print("Source ");
       printArray(source);
       System.out.print("Target ");
       printArray(target);
       System.out.println();

       System.out.println("------------------------TEST linearSearch------------------------");
       int[] array = { 23, 18, 45, 90, 12, 3 };
       int searchElt = 12;
       printArray(array);
       System.out.println(searchElt + " found: " + r.linearSearch(array, searchElt, 0, array.length - 1) + "\n");

       System.out.println("------------------------TEST reverse------------------------");
       printArray(array);
       r.reverse(array, 0, array.length - 1);
       System.out.print("Reverse ");
       printArray(array);
       System.out.println();

       System.out.println("------------------------TEST parityPartition------------------------");
       printArray(array);
       r.parityPartition(array, 0, array.length - 1);
       System.out.println("After parityPartition");
       printArray(array);
       System.out.println();

       int[] array2 = { 2, -1, 3, 4, 8, 5, -7 };
       printArray(array2);
       r.parityPartition(array2, 0, array2.length - 1);
       System.out.println("After parityPartition");
       printArray(array2);
       System.out.println();

       System.out.println("------------------------TEST countRuns------------------------");
       int[] array3 = {4, 4, 4, -2, 0, -8, -8, 3, 3};
       printArray(array3);
       System.out.println("Number of runs: " + r.countRuns(array3, 0, array3.length - 1) + "\n");
      
       printArray(equalArr);
       System.out.println("Number of runs: " + r.countRuns(equalArr, 0, equalArr.length - 1) + "\n");
      
       printArray(emptyArr);
       System.out.println("Number of runs: " + r.countRuns(emptyArr, 0, emptyArr.length - 1) + "\n");
   }
}

SAMPLE OUTPUT:

Array: allEqual: true Array: 1 allEqual: true allEqual: true Array: 1, 1, 2, 1, 1 allEqual: false --TEST arraycopy- Source Array: 1.0, 2.0, 3.0, 4.0, 5.0 Target Array: 11.0, 12.0, 2.0, 3.0, 4.0 Array: 23, 18, 45, 90, 12, 3 12 found: true Array: 23, 18, 45, 90, 12, 3 everse Array: 3, 12, 90, 45, 18, 23 --TEST parityPartition-- Array: 3, 12, 90, 45, 18, 2.3 After parityPartition Array: 23, 45, 3, 12, 90, 18 Array: 2, -1, 3, 4, 8, 5, -7 After parityPartition Array: -7, 5, 3, -1, 2, 4, *8