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 progam 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.
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 mulitplications. 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 prints the number of mulitplications that were required to compute the power. Fill in the code for the recursive power method. Be sure to include code to print the number of multiplications that the method performs. 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.
As we discussed in class, the merge sort algorithm uses fewer comparisons than the selection, insertion, and bubble sort algorithms. But is it also faster? To answer that question we are going to extend the sort timing code that you began in the last lab. The file SortTime.java contains the code that we used in class. The file Sorting.java contains all of the sorting methods we have covered, including merge sort. Take a look at the code for merge sort and make sure that you understand how it uses recursion. Add to the SortTime program the calculation of merge sort's steady state run time. Run the program, how does merge sort perform compared to the other methods? Is this what you expected?
To get a better understanding of how these algorithms differ from each other, it is important to understand how they differ with inputs of varying sizes. Add to the SortTime class code that will compute the steady-state time of each sort method on arrays of five different sizes. Each array size should be the same ammount larger than the array size that is smaller than it. (1200, 1400, 1600, etc...) Print the result as a table.
It would be easier to understand what the differences between these algorithms are if we could visualize them. For the last part of this lab, create code that plots the table of sort algorithm execution times. Put the size of the array on the x-axis and the steady-state time on the y-axis. Each algorithm should be plotted with a different color and each data point should be connected to the one preceeding and following it, if they exist. Include a key that explains what each color means.
Hand In: Tar your lab directory and e-mail it to your instructor with cpsc170 lab7 in the subject.