Assignment 7 Recursions

The goal of this assignment is to get you a lot of practice with recursion, ensure you understand the methodology behind recursion, and that you can identify how a recursive solution works.

Basic Procedures

You must:

• Fill out the readme.txt file with your information (goes in your user folder)
• Have a style (indentation, good variable names, etc.)
• Comment your code well (no need to over do it, just do it well)

You may:

• Add any additional methods you need (though they must be private).

You may not:

• Make your program part of a package
• Use any import statements except for java.util.Dates (not java.util.*)
• Change the method signatures of the provided methods
• Add any additional classes/variables.

Part 1: Recursion Practice

Setup

1. Download the assignment7.zip and unzip it. This will create a folder user-labsectionassignment7

2. Rename the folder replacing user with the first part of your GMU email address and labsection with your lab section.

• Example: krusselc-206-assignment7 (Katherine Russell, Lab Section 206)
• The folder already contains some code.

3. Complete the readme.txt file (an example file is included: exampleReadmeFile.txt)

Task

Fill out the methods in the Assignment7.java file. They should be pretty self explanatory, but there are JavaDoc comments to try to give you some explanation of how the method works, some hints, and some additional restrictions on what you should/shouldn't do.

Unlike previous assignments, Assignment7SampleTests.java is required to get Assignment7.java to work. You'll notice that at the beginning of each method in Assignment7 is the line:

Assignment7SampleTests.hasRecursion();

This line will try to identify for the test cases if you are implementing recursion or not and it is required that all methods have this as their first line. This works with the test cases called ___RecursionCheck(), but please note that this is not how you will be graded on your recursion, so don't try to trick it into passing the test cases. If you really want to print to the console, you can use:

Assignment7SampleTests.sysOut.println();

Though obviously stepping through with the debugger is preferable to this.

Testing

The test cases provided are good indicators of the type of tests that will be used for grading, but make sure to check your edge cases and do some additional testing on your own.

Part 2: Advanced Recursion

Setup

In your user directory, create a file you can insert images into and convert to a PDF easily. For example, a word document or an open office document would be a good choice. DO NOT submit your report in any format other than PDF.

Task

Pick an advanced recursion example and explain it, in detail (at least 300 words), with pictures (pictures that you made, not ones stolen from the internet). Your explanation must include at least three sources you used to learn this (with links) and you must properly cite your work. The 300 words does not include your citations or your title. You may create some pseudocode, but that does not count towards your 300 words (and also can't be stolen from the internet).

What are advanced recursion examples? Here are some ideas (not all of them are good choices for a 300 word explanation): Euclid's algorithm, Towers of Hanoi, Grey code, sudoku, maze solving, some of the creative exercises from here: http://introcs.cs.princeton.edu/java/23recursion/, many different algorithms for trees/graphs, etc. If we haven't talked about some component in this class (such as trees/graphs), make sure you explain that as well.