CS 2401 Assignment #4

Due Date: Thursday, October 6 or Monday, October 10, 2011, depending on the day of your lab.

Objective: The goal of this assignment is to practice recursion.

Assignment. The author of a CS 2401 textbook is trying to predict a honorarium that he will earn for this book. The honorarium is proportional to the number of books sold. In the publisher's experience, this amount follows the power law: the amount of money m(n) earned in year n is equal to m(1) * n, where α is a parameter depending on the book. Once we know the values m(1) and m(2) = m(1) * 2, we can find α from the ratio m(2) / m(1) (hint: use logarithms). One the value α is determined, we now need to compute, for each year N, the total amount of money earned by this year, i.e., the sum

s(N) = m(1) + m(2) + ... + m(N).

Write two methods that, given the values m(1), m(2), and N, predict s(N): a method based on recursion and an iterative method that uses a simple for loop; the ideas behind both methods are explained in similar examples in the class and in the book.

Once the methods are up and running, compare the speed of these two approaches by using the same techniques as in Assignment 3. Record your observations and be able to explain what is happening to your TA when you demo your program.

Testing. Do not forget to test your method. To test your method, pick any value of m(1) and α. For example, if you take m(1) = 100.0 and α = 1.0, then should get m(2) = 100.0 * 2-1 = 100.0 / 2 = 50.0, m(3) = 100.0 * 3-1 = 100.0 / 3 = 33.33..., and m(4) = 100.0 * 4-1 = 100.0 / 4 = 25.0, and thus,

s(4) = m(1) + m(2) + m(3) + m(4) = 100.0 + 50.0 + 33.33... + 25.00 = 208.33...
This means that your program, when you pass it the values m(1) = 100.0, m(2) = 50.0, and N = 4, should return 208.33... as the value for s(N). Specifically, your program should first find α by applying the logarithms to the condition that m(2) / m(1) = (m(1) * 2) / m(1), then compute m(3), m(4), and finally, s(4). Feel free to test your method on other similar examples as well: the more you test, the more confident you will be that your program is correct.