CmSc 150 Fundamentals of Computing I

Laboratory exercise 14: Recursion

Purpose: Practice development of recursive methods

Preparation

Download the project Lab14-Recursion.zip in the folder CMSC150 and unzip it. Rename the project so that its name starts with your first name.

Open Java IDE, open the project, open the program. The project contains a class ArrayRM with recursive array methods and a driver Recursion to test the methods.

Developed methods: createArray, printArray, sumRecursive, insertionSort

Run the program with option 1: recursive sum of the array elements, and study the output to understand how recursion works.

Program development:

  1. Develop a recursive method 
    2. int maxIndexRecursive(int[]array, int numElements)
    that returns the index of the maximal element among the first numElements elements in the array.

    The recursive algorithm is as follows:

    1. Terminating condition
      2. If the number of elements is one, return 0
    2. Recursive rule
      3. Find maxIndex - the index of the greatest element among the first numElements-1 elements in the array.

      If array[maxIndex] is greater than array[numElements-1], return maxIndex, else return numElements-1

    Implementation notes:

    Declare a variable maxIndex to contain the value to be returned, and use one return statement only.
  2. Implement case 2 in the Recursion class

    3. It should perform:

    - call maxIndexRecursive(int[]array, int numElements)
    - print the greatest elements in a message “the greatest element in the array is:…”

    Test the maxIndexRecursive method for an array of 10 elements and for an array of 1 element.

  3. Develop the binary search method
    4. 
int binarySearch(int[] array, int start, int end, int element)

    The recursive algorithm is as follows:

    1. Terminating condition

      2. If the number of elements is one, compare the array element with the element we are looking for.

      If they are equal, return the index of the element
      Else return -1
    2. Recursive rule

      3. Find the middle index in the examined portion of the array

      If the element is smaller then the middle element, search to the left
      If the element is bigger, search to the right
      If the element is equal to the middle element, return its index
  4. Implement case 3 in the Recursion class.

    5. It should perform the following:

    1. Call insertion sort to sort the array, and then print the sorted array
    2. Ask for an element to be found
    3. Call binary search
      • If the returned index is not -1, print a message: “The element X is found at position Y”, where X is the element specified by the user, and Y is its index in the array.
      • If the returned index is -1, print a message “ element X is not found”

    Test the binary search method for an array of 10 elements and for an array of 1 element.
    Test for element found in the first position, in the last position, somewhere in the array, and not found in the array – smaller than all elements, greater than all element, in the range of the elements, but not in the array.

At the end of the lab zip the project folder and sent it to me even if the program is not completed. Do not forget to write your name in the title comment. Follow the rules for submitting assignments. Your grade will be reduced by 10% for each violation.

If the program is not completed, you have to complete it and send it by Thursday 04/20, 5 pm.

Back to CMSC 150 home page