Assignment 7

Due 1/4/2005

 

Solve the following problem with recursion. Note that some of these problems can easily be solved by iterative methods (i.e., with for or while loops). But since the goal of this assignment is to help you practice recursion, you are required to come up with recursive solutions for them.

 

7.1.        Write a program to find the largest element in an array recursively.

7.2.        Write a recursive binary search program.

7.3.        The sequence a(i) is defined below, write a recursive program to compute a(i).

7.4.        The sequence b(i) is defined below, write a recursive program to compute b(i).

7.5.        The sequence c(i) is defined below, write a recursive program to compute c(i).

For problems 7.3-7.5, find the smallest i that overflows a 32-bit integer.

 

Extra point problem.

7.6.        The greatest common divisor of integers x and y is the largest integer that evenly divides both x and y. Write a recursive function gcd that returns the greatest common divisor of x and y (assume x > =y), which is defined recursively as follows: If y is equal to 0, then gcd (x, y) is x; otherwise, gcd(x, y) is gcd(y, x%y), where % is the modulus operator.

 

As before, put all programs in one file and turn it in to http://140.127.194.140. Remember to provide test data and test drivers for each problem. The deadline is midnight, Jan. 4, 2005. Extra points will be given for early birds, so try your best to submit your program as soon as possible.