Objectives: This set of programs will test your skills at formulating, implementing, and understanding recursive solutions to certain problems.

2. Implement the division of two positive integers (X and Y) via repeated recursive subtraction. This function should calculate the quotient and the remainder of X/Y.

3. Consider the following recurrence relation:

f(1) = 1; f(2) = 1; f(3) = 1; f(4) = 3; f(5) = 5;
f(n) = f(n-1) + f(n-5) for all integers n > 5.

a) Using the box-trace method, compute f(n) for the following values of n: 6, 7, 12, 15. Show all work.
b) Implement a C++ function, called ComputeFRecursively, that recursively computes f(n) for arbitrary integer values of n greater than zero.
c) Implement a C++ function, called ComputeFIteratively, that itertively computes f(n) for arbitrary integer values of n greater than zero.
d) Using the segment of code below, time ComputeFRecursively for values of n from 50 to 70. Using Excel or a similar product, create a graph of n versus computation time (T) for ComputeFRecursively.

#include <time.h>

clock_t ltimeBefore, ltimeAfter;
float T = 0.0;
int ans;
for (int i = 50; i < 70; i++) {
   ltimeBefore= clock( );
   ans = ComputeFRecursively (i);
   ltimeAfter = clock( );
   T = ltimeAfter - ltimeBefore;
}

e) The data plotted in part (d) should be approximately expontential. Every exponential function takes the form T(n) = k * aⁿ, where k and a are constants. Using any two data points generated in part (d), determine values for k and a. Calculate T(200).
f) Would you, in practice, use ComputeFRecursively or ComputeFIteratively to determine f(n) for, say, n=200? Why?

4. For those unfamiliar with calculus, integration is used to, among other things, find the area between a curve and the x-axis on a graph. Believe it or not, the area under a curve is useful information; for example, if the curve represents the velocity of an object over time, then the area under the curve represents the distance travelled by that object.

In this problem, you will use an algorithm related to integration to approximate the area between a curve and the x-axis on a graph. The curve of interest is f(x) = x^0.5 + 5, given in the graph below (of course, the x-axis is horizontal and the y-axis, vertical):


By integration, I have determined that the area under our curve from x = 0 to x = 30 is precisely 259.545 (the area is shaded in the graph below):



The area may be approximated, though, by finding the area of the rectangle from x = 0 to x = 30 and from y = 0 to y = f(15) = 8.873. This rectangular area (see shaded area below) is (30)*(8.873) = 266.19.



266.19 is close to the true answer (259.545), but we can do better. Instead of using one rectangle whose width is 30 and whose height is f(15) to approximate the area under the curve, we can use two adjacent rectangles. The left-hand rectangle will have width 15 and height f(7.5)=7.739 and the right-hand rectangle will have width 15 and height f(22.5)=9.743, as in the following graph:



The area of the left-hand rectangle is (15)*(7.739) = 116.085 and the area of the right-hand rectangle is (15)*(9.743) = 146.1645. The sum of these two areas is 116.085 + 146.1645 = 262.2495 and is a better approximation to the true area under the curve than 266.19 -- but we can do better! We can divide the two rectangles in the image above into four rectangles, each with width 7.5. Summing the area of these four rectangles will yield an approximation to the area under the curve that is closer to the true value than 262.2495! But why stop there? We can, in fact, divide the domain from x = 0 to x = 30 into very small rectangles (with, say, widths of 0.01) and sum their areas to get very good approximations to the true area under the curve.

Given this longwinded discussion, your task is to write a recursive function that uses the rectangle-area-method to approximate the area under our curve from x = 0 to x = 30. Your recursive function should stop dividing rectangles when rectangle size reaches 0.001.

Implementation: The above functions should be implemented in the same program and called one after the other. Each function should be recursive not iterative unless otherwise specified.

Input: Unless otherwise specified, select input data that completely tests each recursive function described above.