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 function to determine the nth number in the
sequence. The file fibonacci.py 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 function
compute_nth_fibonacci fib so that it recursively computes and
returns the nth number in the sequence.
Recursive functions 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.py contains a program that reads in
integers base and exponent and computes baseexp
using both a looping and a recursive power function. The looping power
function also calculates and returns the number of multiplications that
were required to compute the power. Fill in the code for the
recursive power function. Be sure to include code that calculates the
number of of multiplications that the function 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 function think about
how you can change your recursive function to have fewer recursive
calls.
The file list_util.py contains list sorting functions you have already written this semester. It also contains three unimplemented functions needed to complete the merge sort algorithm we discussed in class.
Begin by writing the merge function. The function 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 imports list_util and tests the merge
function before proceeding to write the other two functions.
Next, write the two mergeSort functions.
The mergeSort function
with no parameters is the public function that is called from other
classes to sort the array list. This function should simply call the
other _mergeSort function specifying indices for the entire
array. The private _mergeSort function is the recursive
function that calls the _merge function. 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 function.
Two things you
should pay attention to when writing this function. 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.
Finally, modify your sort_timer.py program from the last lab to compare merge sort's speed to insertion sort and selection sort. Which is fastest? Does this make sense?
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.