CSE 131 Module 2: Recursion

Lab


Workspace Update

  1. Update your eclipse workspace to get the lab2 package.
    Update by right-clicking (control-click on Mac) the main project in the package explorer, drag down to Team... and click Update.

    You should see a lab2 package in the src directory.

  2. Most likely, you will see a red 'X' on the lab2 package because the compiler can't find JUnit. In the lab2 package, double click on the file name RecursionTest.java to open it in the editor. You'll see an error marked in the eclipse editor. Click on the light bulb in the left margin next to the error, and one of the choices should be to fix the project setup. Double-click that that and follow from there to add JUnit4 to the build path. This should tell the compiler where to find JUnit, resolving the error.

Warmup

At this point, be sure to ask questions if anything is unclear so far.


Project: Implementing Recursive Functions

You will be writing new methods and JUnit tests in this lab, and this may well be the first time you have done that. You will be patterning what you do after the examples that are already in the files provided for this lab. Try to reason about what you see in the files we provided, and feel free to try things. As always, ask for help as soon as you need it!

Your work will consist of:

  1. Write and test a recursive method sumDownBy2 with the following specification.
    PARAMETERS:   an integer n
    RETURN VALUE: the sum of the positive integers n + (n-2) + (n-4) + ...
    EXAMPLES:     sumDownBy2(7) is 7+5+3+1 = 16
                  sumDownBy2(8) is 8+6+4+2 = 20
                  sumDownBy2(0) is 0
                  sumDownBy2(-1) is 0
    
    • Once you've written code that you think is correct for harmonicSum in your Recursion.java file, then you should write and run a corrsponding @Test method into the RecursionTest.java file.
    • A good name for the test method is testHarmonicSum, and you should put in a few assertEqual tests in testHarmonicSum to make sure your code for harmonicSum is working properly.
    • Make sure you see green for this test before going forward.

    Continue the lab in this fashion: write code, test the code, and then move forward.

  2. Write and test a recursive method harmonicSum with the following specification.
    PARAMETERS:   a positive integer, n
    RETURN VALUE: the sum 1 + 1/2 + 1/3 + ... + 1/(n-1) + 1/n
    
    Warning: When using assertEquals to compare two double types, supply a third parameter to indicate the tolerance.

    For example:

       assertEquals(d1, d2, .01);
    
    compares d1 and d2 with tolerance 1/100. The two doubles will be considered the same if the are within 1/100 of each other.

  3. Write and test a recursive method called geometricSum with the following specification.
    PARAMETERS:   a non-negative integer, k
    RETURN VALUE: the sum 1 + 1/2 + 1/4 + 1/8 + ... + 1/Math.pow(2,k)
    

  4. Write and test a method mult with the following specification without using the multiplication operator. Write a recursive method that performs the multiplication by repeated addition. Make your method work for both positive and negative integers, as well as zero. Start by calling a separate helper method that assumes both parameters are non-negative. Then, in the calling method, make an adjustment afterwards for the case when the signs of the two original numbers were different.
    
    PARAMETERS:   integers j and k
    RETURN VALUE: the product j*k
    

  5. Write and test a recursive method expt with the following specification. Use repeated multiplication. (Do not use the built-in exponentiation method.)
    PARAMETERS:   integers n and k, where k >= 0
    RETURN VALUE: the value of n to the power k
    EXAMPLES:     expt(3,2) is 9
                  expt(5,0) is 1
                  expt(2,5) is 32
    
    Hint: rewrite n^k as n * n^(k-1)

  6. The least common multiple (LCM) of two numbers is the smallest number that is a multiple of both. Write and test a method lcm with the following specification.
    PARAMETERS:   positive integers j and k
    RETURN VALUE: the least common multiple (LCM) of j and k
    EXAMPLES:     lcm(3,5) is 15
                  lcm(6,8) is 24
    
    Hint: Write a helper method with an extra parameter. If j >= k, start the extra parameter at j and keep adding j to it at each recursive call until you reach a value divisible by k. Think about how you can be assured this will terminate.

  7. Write and test a recursive method loanLength with the following specification.
    PARAMETERS:   a loan amount (principal) in dollars
                  an annual interest rate
                  a monthly payment
    RETURN VALUE: the number of months until the loan is paid off,
                  assuming that the interest is compounded monthly
    EXAMPLES:     loanLength(1000, 0.10, 200) is 6 months
                  loanLength(1000, 0.10, 1050) is 1 month
                  loanLength(0, 0.90, 50) is 0 months
    
    Banks charge interest before they deduct payment.
    In the last month, the payment may be less than the monthly payment amount. So, think of the loan as being paid off when principal is 0 or less.

  8. Modify your method in the previous problem to print out the principal remaining at each month. To print a String s to the console, use the line
    System.out.println(s);
    Each line of the output should show the number of months that have gone by and the amount of principle remaining, to the nearest integer. For example, for a $1000 loan with an interest rate of 10% and a monthly payment of $250, the printed output would be as follows:
      Month 0: $1000
      Month 1: $758
      Month 2: $515
      Month 3: $269
      Month 4: $21
    

Submitting your work (read carefully)



Last modified 22:14:02 CST 11 November 2009 by Ron K. Cytron