CPSC 170 Lab 6: Recursion

Fibonacci Numbers

Any code that can be written using recursion can be written using loops. However, sometimes it is easier to program an algorithm using recursion. One case when it is easier to program an algorithm recursively is when it is defined recursively. For example, 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) (for all 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. The file Fib.java contains the skeleton for a program that reads an integer, n, and computes and prints the nth Fibonacci number. Save this file to your directory. Following the specification above, fill in the code for the method fib so that it recursively computes and returns the nth number in the sequence.

Power Function

Recursive methods are also sometimes more efficient. The power function, xy, can be programmed using a loop. But the recursive definition of the power function leads to an algorithm for computing the power function that uses fewer multiplications. The recursive definition is:

x1 = x
xy = xy/2*xy/2 (if y is even and greater than 1)
xy = x*x(y-1)/2*x(y-1)/2 (if y is odd and greater than 2)

The file Power.java contains a program that reads in integers base and exp and computes baseexp using both a looping and a recursive power method. The looping power method calculates the number of multiplications that were required to compute the power using the numberOfMults instance variable. Fill in the code for the recursive power method. Be sure to include code that calculates the number of of multiplications that the method performs using the numberOfMults instance variable. Test your code and compare the number of multiplications, is it what you expected? If the number of multiplications is the same for each method think about how you can change your recursive method to have fewer recursive calls.

Graphing Sort Times

The file Array.java contains a class with a method stub for merge sort that you should complete. The method should use the merge method, which is also defined in the Array class. Once you have completed the method, be sure to test it before moving on.

How does the merge sort algorithm compare to the selection, insertion, and bubble sort algorithms in terms of speed? To determine this we could find the steady state run times of each of the algorithms, but this will only tell us how they perform for finite inputs. In order to determine how they will perform for very large inputs we can graph their performance on increasingly large arrays in order to find a trend.

Create a program GraphSortTime that will compute the average sort time of each of the sorting methods for arrays of varying sizes. The array sizes should be even spaced, 1000, 2000, 3000, etc. You do not have to compute the steady state sort time as you did in lab 4. Instead approximate the steady state by averaging the number of sorts that were necessary to achieve steady state in lab 4. The calculation of the sort times should not be in the paint method. This would cause the program to freeze every time the operating system redraws the window. Instead they should be calculated once when the program first runs, and then saved in an array that is read by the paint method.

The paint method should plot each of the sort times using a line graph. The x-axis represents the size of the array, and the y-axis represents the search time in milliseconds. Each average sort time can be plotted in the window as a point where its x coordinate is determined by the size of the array and the y coordinate is determined by the average number of milliseconds it took to sort the array. You can invert the y coordinate if you want the origin of the graph to be in the lower left corner instead of the upper left. Choose a different color for each algorithm and draw a line between each consecutive data point. That is, draw a line between the point for sorting an array of 1000 elements to the point for 2000 elements, a line between the point for 2000 elements and the point for 3000 elements, etc. Include a key that explains which algorithm corresponds to which color.

To submit your code: Tar the files in your lab6 directory and copy the tgz file to the directory /home/staff/bouchard/CPSC170A/lab6. Be sure to name the tar file with your names, not lab6.tgz.