CPSC 170 Lab 6: Introduction to Recursion

As usual, create a lab6 subdirectory for today's lab, open this document in FireFox, and start eclipse.
  1. Computing a positive integer power of a number is easily seen as a recursive process: 
    x0 = 1
xy = x*xy-1  for all y > 1
    File Power.java contains a main program that reads in integers base and exp and calls method power to compute baseexp. Fill in the code for power to make it a recursive method to do the power computation.

    Print Power.java.

  2. The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. More specifically, if fib(n) is the nth term of the sequence, then the sequence can be defined as follows: 
        fib(0) = 0
    fib(1) = 1
    fib(n) = fib(n-1) + fib(n-2)  n>1
    For example, the first eight elements of the sequence are 0,1,1,2,3,5,8,13.

    Because the Fibonacci sequence is defined recursively, it is natural to write a recursive method to determine the nth number in the sequence. File Fib.java contains the skeleton for a program that reads an integer n from and computes and prints the nth Fibonacci number. Save this file to your directory. Following the specification above, fill in the code for method fib so that it recursively computes and returns the nth number in the sequence.

    Print Fib.java.

  3. One algorithm for converting a base 10 number to base b involves repeated division by the base b. Initially one divides the number by b. The remainder from this division is the units digit (the rightmost digit) in the base b representation of the number (it is the part of the number that contains no powers of b). The quotient is then divided by b on the next iteration. The remainder from this division gives the next base b digit from the right. The quotient from this division is used in the next iteration. The algorithm stops when the quotient is 0. Note that at each iteration the remainder from the division is the next base b digit from the right -- that is, this algorithm finds the digits for the base b number in reverse order.

    Here is an example for converting 3010 to base 4: 

                          quotient       remainder
                      --------       ---------
         30/4 =           7              2
	 7/4  =           1              3
	 1/4  =           0              1
    The answer is read bottom to top in the remainder column, so 3010 = 1324.

    Think about how this is recursive in nature: If you want to convert x (30 in our example) to base b (4 in our example), the rightmost digit is the remainder x % b. To get the rest of the digits, you perform the same process on what is left; that is, you convert the quotient x / b to base b. If x / b is 0, there is no rest; x is a single base b digit and that digit is x % b (which also is just x).

    The file BaseConversion.java contains the shell of a method convert to do the base conversion and a main method to test the conversion. Note that the convert method returns a string representing the base b number. This means that in the base case, when the remainder is what is to be returned, it must be converted to a String object by concatenating it with a null string. Similarly, in the recursive case the result of the recursive call will be concatenated with the remainder.

    Fill in the code for convert and the call in the main method. Here is some data to test your program on:

    Print BaseConversion.java.

  4. As we discussed in class, MergeSort is a sorting algorithm that is more efficient that Insertion Sort or Selection Sort. It achieves this speed up by repeatedly dividing the list in half and sorting the sublists. When you reach a list that has only one element, you know that it is sorted. We know that the list will be divided at most log2 (n) times, where n is the number of elements in the list. Once we have the sorted lists, it is very easy to combine them; that is an O(n) operation. This process clearly lends itself to a recursive implementation.

    The file Sorting.java contains the a skeleton of the MergeSort (as well as the other sorts). The file TimeSorts.java is the familiar driver for these sorting routines. Download them both to your directory. Fill in the code to complete the mergeSort (as directed by comments), and add an option to TimeSorts that allows you to execute and time MergeSorts.

    Make sure that your MergeSort is working by printing out a sorted list (Option 1 on the menu).

    Download the file SortingCompare2.ods to your directory. Open this file using OpenOffice Spreadsheet. You will see a worksheet similar to lab4. Conduct sorts on the appropriate list sizes and record your data. What does the chart tell you about the efficiency of MergeSort relative to Selection Sort and Insertion Sort? (write your answer in the spreadsheet). Save the worksheet and print a copy of your graph.

HAND IN: