Data Abstraction & Problem Solving with C++ Ch. 8 Exercise 12

Repeat Exercise 21 in Ch. 2, using the ADT list to implement the function f(n).

Exercise 21:

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) + 3 x f(n-5) for all n > 5.

a. Compute f(n) for the following values of n: 6, 7, 12, 15

b. If you were careful, rather than computing f(15) from scratch (the way a recursive C++ functiong would compute it), you would have computer f(6), then f(7), then f(8), and so on up to f(15), recording the values as you computed them. This ordering would have saved you the effort of ever computing the same value more than once. (Recall the iterative version of the rabbit function discussed at the end of this chapter).

Not that during the computation, you never need to remember all of the previously computed values - only the last five. Taking advantage of these observations, write a C++ function that coputes f(n) for arbitrary values of n.