Lab: Experimenting with Recursion

Instructions: Answer the following questions one at a time. After answering each question, check your answer (by clicking on the check-mark icon if it is available) before proceeding to the next question.

Getting Ready: Before going any further, you should:

Depending on your development environment, create either a directory or a project for this lab.
Setup your development environment.
Download the following files:

../experience_recursion-tracing/Extreminator.java
../experience_recursion-tracing/ExtreminatorDriver.java
DirectoryListing.java
DirectorySizeCalculator.java
../experience_recursion-tracing/Searcher.java

to an appropriate directory/folder. (In most browsers/OSs, the easiest way to do this is by right-clicking/control-clicking on each of the links above and then selecting Save as... or Save link as....)
Add the appropriate files you downloaded to the directory/project you created for this lab.
.java Files: In most IDEs, .java files (i.e., source files) can just be copied into the project.

.class and .jar Files: In some IDEs it is easier to use .class files and in others it is easier to use a .jar file that contains the .class files. Hence, you have been provided with both. See the course "Help" page on your IDE for more information.

Resources: In some IDEs, resources (e.g., images, data files) need to be in a special directory whereas in others they need to be in the working directory. See the course "Help" page on your IDE for more information.

For a variety of reasons (that you either already understand because we have covered parameterized classes/interfaces or will understand later in the semester when we do), you will get a warning when you compile some of the classes that says something like:

  ... uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.

You can and should just ignore this warning.

1. Common Mistakes: This part of the lab will help you understand the kinds of mistakes that you might make when developing recursive algorithms.

Open the Extreminator.java and ExtreminatorDriver.java files.
Compile and execute the ExtreminatorDriver. What output was generated?
.
The answer is: 6
What is the definition of the word "infimum"? (Look it up if you don't already know it.)
.

"Infimum" means the greatest lower bound.
In math, the abbreviation \(\text{inf}\) is often used as an abbreviation for "infimum". Give another (closely related) example of this kind of abbreviation in math.
.

min is often used as an abbreviation for "minimum". This is a very closely related example since the minimum and the infimum are the same for closed sets.
Given your (perhaps newfound) understanding of the infimum, is the output correct?
.

Yes. 6 is, indeed, the minimum of the set \(\{10, 8, 22, 58, 6, 75, 11\}\).

Change the refinement portion of the private findInf() method to the following:

  	    // Refinement -- start at the next index
  	    if (values[startIndex] < soFar)
  	    {
  		soFar = values[startIndex];
	    }

	    soFar = findInf(values, startIndex, soFar);

Re-compile and re-execute the driver. What error message was generated?


                                    java.lang.StackOverflowError
	at Extreminator.findInf(Extreminator.java:46)

Why was this error message generated?
.

The refinement step is not actually doing any refining. Hence, this is an infinite recursion.

Change the refinement portion of the private findInf() method to the following:

	    // Refinement -- start at the next index
	    if (values[startIndex] < soFar)
	    {
		soFar = values[startIndex];
	        soFar = findInf(values, startIndex+1, soFar);
	    }

Re-compile and re-execute the driver. What output was generated?
.
The answer is: 8
Why was this incorrect output generated?
.

The recursive call is only made when values[startIndex] is less than soFar. This is true for 10 and for 8 but not for 22. Hence, the recursion stops at that point.

Change the refinement portion of the private findInf() method to the following:

	    // Refinement -- start at the next index
	    if (values[startIndex] < soFar)
	    {
		soFar = values[startIndex];
	        soFar = findInf(values, startIndex, soFar);
	    }

Re-compile and re-execute the driver. What output was generated?
.
The answer is: 10
Why was this incorrect output generated?
.

values[startIndex] is less than soFar. In addition, startIndex is not changed.

2. Writing Simple Recursive Algorithms: This part of the lab will help you get better at writing recursive algorithms.

Create a class named WordGames. (This will be a utility class.)
Add an empty public static method named occurrences() to the WordGames class. It must return an int and be passed two String parameters named pattern and source.

What code did you add?

                                    
    public static int occurrences(String pattern, String source)
    {
    }

Think about the problem of determining how many times one String (called the pattern) occurs in another String (called the source).
What is the easy case for this problem? In other words, for what source objects is this problem really easy? (Hint: Think about properties of the source objects, not the specific values.)
.

When the source has 0 length.

Add code to the occurrences() method to handle this case. (Note: Your code may not use any methods in the String class other than the length() method.) What code did you add?

                                    
       if (source.length() == 0) // The easy case
       {
          return 0;
       }

The hard cases are, obviously, all of the other cases. How can you refine the hard cases? In other words, how can you take a hard case and make it easier (i.e., move it closer to the easy case)?
.

Check if it starts with the pattern and then remove the first character.

Add code to the occurrences() method to handle your refinement process. Remember, you must both move the parameter closer to the base case and move the answer closer to the correct answer. (Note: Your code may not use any methods in the String class other than the substring() and startsWith() methods.) What code did you add?

                                    
       else                      // Refinement
       {
          int    count;          
          String smaller;
          
          smaller = source.substring(1); // Move the parameter closer

          count = 0;          
          if (source.startsWith(pattern)) count = 1;
          
          return count + occurrences(pattern, smaller); // Move the answer closer
       }

Write a driver or JUnit test and test your occurrences() method using the following cases:

    n     intelligent
    i     intelligent
    p     hippopotomonstrosesquippedaliophobia
    ed    educated
    meow  homeowner

3. Writing Recursive Algorithms for Hierarchical Systems: This part of the lab will help you get even better at writing recursive algorithms. In particular, it will help you understand how recursion can be useful when working with hierarchical systems.

Copy the file Extreminator.java into the working directory (i.e., the project directory, not the src directory or default package directory, if you are using Eclipse) so that this directory has a file in it. (You can use another file if you like, and you can have more than one file in the working directory, just make sure they do not have a size of 0.)
Open the DirectoryListing class.
Compile and execute the DirectoryListing class.
Modify the DirectoryListing class so that it prints the size of each file next to the name. (Hint: Use the length() method.) What code did you add?
.
System.out.print(list[i].getName() + "\t" + list[i].length() + "\t");
Compile and execute the DirectoryListing class.
Which sizes are "correct" and which are "incorrect"?
.

The files have the correct size; the directory does not.
Make sure you understand the DirectoryListing class -- you will need to use what you learned from it in the following steps.
Open the DirectorySizeCalculator class.
Review the documentation for the File class and convince/remind yourself that there are two different kinds of File objects, "directories" and "normal files".
From the standpoint of the search(File) method in the DirectorySizeCalculator class, what is the easy case?
.

When contents[i] is not a directory.
What code do you need to add to check to see if case i is the easy case?
.
if (!contents[i].isDirectory())
What processing do you need to do to handle the easy case? (Hint: You need to increase the count of the number of other files and you need to increase the total size.)
.
{ numberOfOtherFiles++; totalSize += contents[i].length(); }

What code do you need to add to refine the hard cases?


                                    	    else // Refine the hard case
	    {
		numberOfDirectories++;
		search(contents[i]);
	    }

Write a driver or JUnit test and test your implementation.

4. Using Care During Refinement: This part of the lab will help you understand why it is very important to be careful during the refinement process.

Review the Searcher class.
What general strategy does the search() method use to shrink the search space?
.

It divides the search space in half.
One might refine the search space by dividing it into quarters. Given first and last, and letting the quarters be defined by first to a, a+1 to b, b+1 to c, and c to last, write expressions for a, b, and c. (Hint: Calculate b (i.e., the middle index) first and then use it to calculate a and c.)
.
b = (first + last) / 2; a = (first + b) / 2; c = (b + last) / 2;
Suppose first is 0 and last is 8. What are a, b, and c?
.

b is 4, a is 2, and c is 6.

Given these values of a, b, and c what would the four calls to the search() method be? (Note: Don't use variables, use literals.)


                                        q1 = search(0, 2, target, data)
    q2 = search(3, 4, target, data)
    q3 = search(5, 6, target, data)
    q4 = search(7, 8, target, data)

Suppose first is 0 and last is 2. What are a, b, and c?
.

b is 1, a is 0, and c is 1.

Given these values of a, b, and c what would the four calls to the search() method be? (Note: Don't use variables, use literals.)


                                        q1 = search(0, 0, target, data);
    q2 = search(1, 1, target, data);
    q3 = search(2, 1, target, data);
    q4 = search(1, 2, target, data);

Which of these calls will cause a failure?


                                        q3 = search(2, 1, target, data);

What is the advantage of dividing (each dimension of) a search space in half?
.

You can almost always divide each dimensions of a search space in half and, when you can't, it is easy to find and fix problems.
Does this mean it is never appropriate to use quarters?
.

Not at all. In fact, if you have a two-dimensional search space then dividing each dimension in half divides the entire space into quarters. Similarly, if you have a three dimensional search space then dividing each dimension in half divides the entire search space into eighths.
What's the big lesson to be learned?
.

Be thoughtful and careful when you write recursive algorithms. Then trace them to make sure you understand how they work. Then test them to make sure they work properly.