Restrictions: you cannot use any methods from the Java Array(s) class to copy an array, check for equality, or otherwise manipulate an array.

You cannot import the Java ArrayList class.

You MAY implement any of the classes from Chapter 3 if needed. To implement any of these classes you must transcribe the code from the textbook. You cannot import the corresponding class from a Java library.

You will need to use (import):

• the Java File class. You may use any of the methods that are available in the Java File class in developing your algorithm. In particular, you should need to use the:
  • java.io.File
  • java.io.FileNotFoundException
• the Java Scanner class

Be sure to read the entire assignment before you begin.

Create a NetBeans project using the convention Lab103-LastFM and ensure it is saved to a location like desktop or your flash drive. In the project you will do the following:

Create a Recursion Class that will implement the following recursive algorithms:

• Recursive algorithm 1:
• Implement a recursive algorithm to compute the number of moves required to solve the Tower of Hanoi puzzle for a given number of discs.
• The number of moves required is defined by the following function:

1 if n = 1

hanoi( n ) =

2 * hanoi( n 1 ) + 1 if n > 1

• The Tower of Hanoi consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
• The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
  • Only one disk can be moved at a time.
  • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  • No larger disk may be placed on top of a smaller disk.

• Recursive algorithm 2:
• Implement a recursive method with the signature

void find( String filename, String startPath )

that finds and prints absolute paths for all entries of the files named filename starting at startPath.

• A startPath may look something like C:\Documents\NetBeansProjects
• A filename name could be Client.java
• The results might be:
  • C:\Documents\NetBeansProjects\Lab101\src\Client.java
  • C:\Documents\NetBeansProjects\Lab102\src\Client.java
  • C:\Documents\NetBeansProjects\Lab103\src\Client.java
• If no matches are found an appropriate message should be printed.
• Note that your method needs to recursively search the directory indicate by startPath and all of its subdirectories.

• Recursive algorithm 3:
• Implement a recursive method for Euclidean algorithm, which computes the greatest common divisor of two integers.
• The Euclidean function can be defined as:

x if y = 0

gcd( x, y ) =

gcd( y, remainder( x / y ) ) if y > 0

Create a Client Class that will fully test each of the recursive methods that you created above in an interactive menu fashion. This class should:

• Presents the user with a menu/list of available recursive methods.
  • The last option in the menu/list should allow the user to quit the program.
• Let the user select which method to test.
• Ask the user for the necessary inputs to test the method.
• Run the selected function and display the appropriate output.
• After the results have been displayed your Client should redisplay the menu/list giving the user the opportunity to try retry the method just run, try a different method or quit the program.
• Your Client (via the menu/list) should allow the user to run the recursive functions in any order and as many times as they like without exiting the program.
• If the user selects an invalid option from the menu/list, the program should inform the user of their mistake and allow them to try again

• For each recursive technique, ask the user for any parameters/values needed for the test.
  • For the find method, the path to a file includes the dive letter (on Windows systems), all directories from the root, and the filename. Each element of the path is separated with the appropriate delimiters, e.g. \ of a Windows system.
• For some of the methods you may find it useful to:
  • Create a calling method that
    • gets the necessary parameters/values from the user, and
    • then calls the recursive methods.
• This approach will allow you to write and test the recursive algorithm independent of user input, data transformation and error checking.
• This approach should keep the code for the recursive method simple and easy to write.

When you test your client be sure to:

• A successful run for each recursive method
• Be sure that the output of each run is meaningful.
  • Just displaying integer values is not acceptable.
• An example of each way that your program catches bad/invalid user input.