Lab 16: Experimenting with Recursion

It may be helpful to work with a partner on this lab. You may submit one copy of the lab with both students’ names on top. Do not “divide and conquer”. You will need this material for the Wednesday exam. Be sure that both partners have a copy of your original work for studying.

Getting Ready: Before going any further you should:

A. Make a directory on your N: drive for this lab.

B. Setup your development environment.

C. Download the file named Extreminator.java

D. Download the file named ExtreminatorDriver.java

E. Download the file named ChangeMaker.java

Part I: This part of the lab will help you understand how to trace the execution of a simple recursive method.

1. Trace the execution of ExtreminatorDriver (showing all of your work).

2. What would be output?

3. Suggest a better name for the findInf() methods.

Part II: This part of the lab will help you understand the kinds of mistakes that you might make when developing recursive algorithms.

4. Execute the ExtreminatorDriver. What output was generated?

5. Change the refinement portion of the private findInf() method to the following::

// Refinement -- start at the next index

if (values[startIndex] < soFar)

{

soFar = values[startIndex];

}

soFar = findInf(values, startIndex, soFar);

Re-compile and re-execute the driver. What error was generated and why?

6. Change the refinement portion of the private findInf() method to the following::

// Refinement -- start at the next index

if (values[startIndex] < soFar)

{

soFar = values[startIndex];

soFar = findInf(values, startIndex+1, soFar);

}

Re-compile and re-execute the driver. What output was generated and why?

7. Change the refinement portion of the private findInf() method to the following::

// Refinement -- start at the next index

if (values[startIndex] < soFar)

{

soFar = values[startIndex];

soFar = findInf(values, startIndex, soFar);

}

Re-compile and re-execute the driver. What output was generated and why?

Part III:

8. Trace the execution of the change() method in the ChangeMaker class when it is passed the array {1, 5, 8} and the value 4. Show all of your work.

9. Modify the ChangeMaker class so that it keeps track of the number of time the change() method is called. What changes did you make?

10. Create a driver that calls the change() method passing it the array {1, 5, 8, 10} and the value 13.

What was output?

How many functions calls were made?

Part IV: This part of the lab will let you try to create a recursive algorithm. This is a simple interest compounding problem. 10% interest compounded annually means that the principle amount each year is increased by 10%. The next year the interest is based on the original amount + 10% interest, and so forth.

4.  An amount of $500 is invested in an account paying 10% interest compounded annually.

a. write a recursive definition for P(n), the amount in the account at the beginning of the nth year. (Write this definition as a function in a class called Interest.java.)

Once it is working, copy the code for your function here:

b. after how many years will the account balance exceed $700? (Use a driver to test your method).