The purpose of this lab is to give you experience with using recursion to solve problems. You will also have a chance to use arrays. Note that in this lab you will be graded on your ability to simplify the problem by using recursion, not just on your completion of the problem. You should focus on using methods to abstract away complexity as well as using recursion.
Imagine you are developing a contact list application for a mobile device. One of the functions you will likely need is a function which can take a list of names and put them in order. For this lab you will do precisely that:
The data file will look something like this:
Minnie Mouse Scrooge McDuck Donald Duck Mickey Mouse Max Goof
You should display the data in sorted order:
Donald Duck Max Goof Mickey Mouse Minnie Mouse Scrooge McDuck
You will want to use an array to store the names. See section 6.1 of the book for information on using arrays. For our purposes, you can assume that we will never have more than 100 names.
To sort the list of names you will use an algorithm called a merge sort which by nature requires a recursive implementation. The algorithm essentially works by recursively splitting a list into sublists and then recombining the sorted sublists. See the link to wikipedia for more information about how the merge sort algorithm works.
The key to recursive programming is in thinking about a way to solve the problem using a smaller version of the same problem. So, if you think about sorting, consider solutions where you sort a part of the list and then assume the rest is sorted in order to create a fully sorted list.
Make sure you use methods to solve parts of the problem so that the overall problem is not so complex.
Some useful functions:
Keep in mind that when java compares strings, an upper case letter will always be “greater” than a lower case letter. Thus 'A' is greater than 'z' but less than 'Z'.
Decomposing the problem using methods will make your code easier to read, easier to debug, and in some cases shorter. Aside from preventing code duplication, creating your own method allows you to create a single, clear command from multiple obscure commands, thereby making it easy to see what your code should be doing. A good way to identify when it is appropriate to create a method is if you see a block of 5-10 lines of code that all work to accomplish a single task. For example, finding the index in an array which contains the lowest string. Recursion will inherently require you to create at least one method, but using methods in general is a very good habit to get in to.
You will prompt the user for the needed file name. You will need to create your own test files in order to assure that your code is working. We have created a wiki page with information about where to put files in order for your eclipse program to find them.
Just as when you were scanning websites, java will want you to deal with the possibility that the Scanner object cannot find the specified file. To resolve the error you will notice that Eclipse gives you two alternatives: add a throws statement or surround with try/catch. For now you can simply throw the error rather than the try/catch alternative. TAs will only run real file paths on your code.
When you have your program working, you will need to show it to a TA. The TA will evaluate your code based on the following criteria:
Extra Credit: Prompt user for option of doing a reverse sort (i.e. z to a) (2 points)
Extra Credit: Sort by last name and then first name (3 points)