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.
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 Pow.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.
The files ArrayList.java and SortableList.java contain the list implementation we have used in several assignments this semester. It also contains three unimplemented methods needed to complete the merge sort algorithm we discussed in class. Complete these methods and test your merge sort algorithm. Modify your SortingTime program from the last lab to compare merge sort's speed to the other sorting algorithms.
To submit your code: Tar your lab6 directory and submit your code on the course Inquire site.