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 file ArrayList.java contains 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.
merge method. The
method takes three indices that specify two adjacent sub
arrays that are sorted and merges the two sub-arrays into one
sub-array that is sorted. Write a program that tests this
function before proceeding to write the other two
functions.mergeSort methods.
The mergeSort method with no parameters is the
public method that is called from other classes to sort the
array list. This method should simply call the
other mergeSort method specifying indices for the
entire array. The private mergeSort method is
the recursive method that calls the merge method.
It should compute the index of the middle element and
call mergeSort on the sub-array to the left of the
middle element and the sub-array to the right of the middle
element. Then the two sub-arrays should be merged, using
the merge method. Two things you should pay
attention to when writing this method. First, the calculation
of the middle index should work if the length of the sub-array
is odd or even. Second, the program must prevent infinite
recursion from occurring.Submit a zip file of your code on the course Inquire site that uses your last names as the file name.