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.