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).

answer = findInf {10, 8, 22, 58, 6, 75, 11}

 

 inf = findInf ({10, 8, 22, 58, 6, 75, 11},0, 2147483647 )

 

  values.length  7

  startIndex     0                

  soFar          2147483647  10

 

   soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 1, 10)

  values.length  7

  startIndex     1                

  soFar          10   8

 

   soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 2, 8)

   values.length  7

  startIndex     2                

  soFar          8

 

   soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 3, 8)

   values.length  7

  startIndex     3                

  soFar          8

 

   soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 4, 8)

   values.length  7

  startIndex     4              

  soFar          8  6

 

    soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 5, 6)

   values.length  7

  startIndex     5              

  soFar          6

 

    soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 6, 6)

   values.length  7

  startIndex     6              

  soFar          6

 

    soFar = findInf({10, 8, 22, 58, 6, 75, 11}, 7, 6)

   values.length  7

  startIndex     7              

  soFar          6

 
  1. What would be output?

The answer is:  6
  1. Suggest a better name for the findInf() methods.

findSmallest

 

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

  1. Execute the ExtreminatorDriver. What output was generated?

The answer is: 6
  1. 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?

Ï «Ï ----jGRASP exec: java ExtreminatorDriver5
ÏϧÏ
ÏϧÏException in thread "main" java.lang.StackOverflowError
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at Extreminator5.findInf(Extreminator5.java:46)
ÏϧÏ_at …

 

  1. 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?

The answer is: 8

 

  1. 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?

The answer is: 10

 

Part III:

  1. 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.

Answer returned is 4  -- see html trace   or   word trace

 

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

Added a class variable called count  and incremented it inside change method.

 

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

What was output?

2

How many functions calls were made?

889

 

 

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:

public class ComputeInterest
{

public double compute (double principle, double rate, int time)
{
 
  if (time == 0)
     return principle;
  else
     return compute ((1 + rate)* principle,rate, time-1);
 }
}

 

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

4