1. Let's first write a nice little program to list all the files in
   your directory.  Call it FileLister.

import java.io.File;

public class FileLister {
    public static void list (File dir) {
	File[] fileList = dir.listFiles();
	for (File f : fileList) {
	    System.out.println(f.getPath());
	}
    }

    public static void main (String[] args) {
	File home = new File(".");
	list(home);
    }
}


  ``.'' is the name of the current directory.  The list(dir) method
  calls dir.listFiles() which returns an array of references to File
  objects for each file (and/or directory) in dir.

  Try running it.  What do you get?

  To run it in your home directory:

cd
java -classpath prog10 FileLister

  The ``-classpath prog10'' means look in the directory prog10 for the
  FileLister class file.

  What do you get?  Ask questions if you do not understand.


2. Now suppose you want to see ALL of your files no matter how deep,
   not just the ones in your home directory.  So instead of just
   printing prog01, you also want the program to print the contents of
   prog01, and so forth.

   What does list do?  It prints out the files in dir.

   We also want it to print out the names of files in each directory
   in dir.  How can it do this?  Is there a method it can call to
   print out the names of files in a directory?

   Yes!  It can call the list method!  After all, it can call any
   (static) method in FileLister.  Why not call itself?  This is
   called RECURSION.

   So add the following lines inside its loop and after it prints
   f.getPath().

	    if (f.isDirectory())
		list(f);

   That says:  if f is a directory, (call list to) print out all the
   files and directories in f.

   But wait...that call to list will do the same thing and call list
   to print out all the files in all the directories in f.  And so on
   and so on.

   Try it!

   The right way to think of it is as follows.

   A. I want a method that will print out all the files and
      directories in a given directory, no matter how deep.

   B. Let's call this method ``list'' and ASSUME that I will
      EVENTUALLY get it working.

   C. Now look at list as written.  It clearly prints out all the
      files and directories dir, right?  It also calls list(f) for
      every member of dir that is also a directory.

      Assuming THAT call to list works, it will print out all the
      files and directories in f, no matter how deep.  Since we do
      this for each f in dir that is also a directory, we must print
      out all the files in dir, no matter how deep.

   D. If the list method works, then it works.  Therefore it works.


3. For the previous example, I could challenge you to write a program
   that do what FileLister does but without using recursion.

   Let's do another example, but this time it will be something you
   already know how to do--sorting.

   Write a program Sorter.java.  Give it a method

    public static ArrayList<Integer> sort1 (ArrayList<Integer> array) {

   However, let's not change array.  Instead declare and initialize
   sorted to a new ArrayList of Integer.  Using the new kind of
   for-loop, add every element of array to sorted.  Ask the TA for
   help if you have trouble.

   Now use the loops over i and j and swapping to sort sorted.  Return it.

   In main, initialize int n to 10.  Declare and initialize an
   ArrayList of Integer named array.  Add n integers to it randomly
   selected from 0 to n-1.

   You can print out array using System.out.println.  (That's another
   advantage of ArrayLists!)  Then print ``start'', call sort1, put
   its output into sorted1, print ``end'', and print the output.  It
   should look something like this.

java Sorter
array = [4, 2, 9, 4, 4, 0, 7, 0, 6, 3]
Start sort1...
...end sort1.
sorted1 = [0, 0, 2, 3, 4, 4, 4, 6, 7, 9]


4. Now start a new sort method sort2.  Like sort1, it should create
   sorted.  However, if array is empty, it should return sorted...end
   of story.  This is ESSENTIAL: it should return immediately if array
   is empty.

   If it hasn't returned yet, it should create three new ArrayList of
   Integer: lesser, same, and greater.

   Go through the elements of array.  If an element is is less than
   array.get(0), add it to lesser.  If it is greater than
   array.get(0), add it to greater.  Otherwise, add it to same.
   Naturally, array.get(0) will be added to same.

   So if 

array = [4, 2, 9, 4, 4, 0, 7, 0, 6, 3]

   then

lesser = [2, 0, 0, 3]
same = [4, 4, 4]
greater = [9, 7, 6]

   Now, sort lesser and put the result in sortedLesser.  Sort greater
   and put the result in sortedGreater.

sortedLesser = [0, 0, 2, 3]
sortedGreater = [6, 7, 9]

   How should you sort?  Call sort2!

   Add the elements of sortedLesser to sorted.  Add the elements of
   same to sorted.  Add the elements of sortedGreater to sorted.  Now
   sorted will be

sorted = [0, 0, 2, 3, 4, 4, 4, 6, 7, 9]

   which is the result of sorting array.

   In main, add code to test sort2 on array.  So when you run the
   program, it should look like:

java Sorter
array = [4, 2, 9, 4, 4, 0, 7, 0, 6, 3]
Start sort1...
...end sort1.
sorted1 = [0, 0, 2, 3, 4, 4, 4, 6, 7, 9]

array = [4, 2, 9, 4, 4, 0, 7, 0, 6, 3]
Start sort2...
...end sort2.
sorted2 = [0, 0, 2, 3, 4, 4, 4, 6, 7, 9]


5. So we used recursion to sort.  But we already know how to sort!
   Big deal!

   Now, comment out the printing of the arrays in main because we are
   going to make them much bigger.  Change the value of n from 10 to
   10000.

   Compile and run your program.  Notice something?  Try 20000 then
   30000.