Lab: Recursion on NaturalNumber – Instance Methods

Objective

In this lab you will practice recursion on NaturalNumbers by implementing the subtract and power instance methods in a new class that extends NaturalNumber2.

Setup

Follow these steps to set up a project for this lab.

1. Create a new Eclipse project by copying ProjectTemplate. Name the new project RecursionOnNaturalNumber2.
2. Open the src folder of this project and then open (default package). For this lab, you will need two files. As a starting point you can use any of the Java files. Rename one NaturalNumberInstanceOps and another one NaturalNumberTest and delete the other files from the project.
3. Follow the link to NaturalNumberInstanceOps.java, select all the code on that page and copy it to the clipboard; then open the NaturalNumberInstanceOps.java file in Eclipse and paste the code to replace the file contents. Save the file.
4. Follow the link to NaturalNumberTest.java, select all the code on that page and copy it to the clipboard; then open the NaturalNumberTest.java file in Eclipse and paste the code to replace the file contents. Save the file.

Method

1. In NaturalNumberInstanceOps.java, complete the body of the subtract method. The contract is available in the NaturalNumber component documentation. For this method you can use any of NaturalNumber methods (except just making a single direct call to subtract as your implementation). The code for add is provided as an example of a recursive instance method on NaturalNumber.
2. Run the NaturalNumberTest program and test your implementation of subtract.
3. Back in NaturalNumberInstanceOps.java, complete the body of the power method. The contract is available in the NaturalNumber component documentation. For this method you can use any of NaturalNumber methods (except just making a single direct call to power as your implementation). Make sure you implement the fast recursive powering algorithm discussed in class (Slides #54-57 in Recursion: Thinking About It).
4. Again run the NaturalNumberTest program and test your implementation of power.

Additional Activities

1. Using recursion implement the multiply instance method (see NaturalNumber). You will need to use add as well as the kernel methods.
2. Implement the power instance method using the fast powering algorithm but without using recursion. Good luck!