// search the last half of the list
index = _______________________________________________;
}
return index;
}
Optional: The binary search algorithm “works” (as in does something) even on a list that is not in order. Use
the algorithm on an unsorted list and show that it may not find an item that is in the list. Hand trace the
algorithm to understand why.
// *****************************************************************
// IntegerListB.java
int[] list; //values in the list
// ————————————
// Creates a list of the given size
// ————————————
public IntegerListB (int size)
{
list = new int[size];
}
// ————————————————————-
System.out.println(i + “:\t” + list[i]);
}
// ——————————————————————
// Returns the index of the first occurrence of target in the list.
// Returns -1 if target does not appear in the list.
// ——————————————————————
Chapter 12: Recursion 239
// —————————————————————–
// Returns the index of an occurrence of target in the list, -1
// if target does not appear in the list.
// —————————————————————–
public int binarySearchRec(int target)
{
return binarySearchR (target, 0, list.length-1);
}
// —————————————————————–
// Recursive implementation of the binary search algorithm.
public void selectionSort()
{
int minIndex;
for (int i=0; i < list.length-1; i++)
{
//find smallest element in list starting at location i
minIndex = i;
240 Chapter 12: Recursion
//
// Provides a menu-driven tester for the IntegerList class.
// (Version B – for use with the binary search lab exerice)
//
// ***************************************************************
import java.util.Scanner;
public class IntegerListBTest
{
{
dispatch(choice);
printMenu();
choice = scan.nextInt();
}
}
// —————————————————
// Does what the menu item calls for.
{
case 0:
case 1:
System.out.println(“How big should the list be?”);
case 2:
case 3:
System.out.print(“Enter the value to look for: “);
case 4:
System.out.print(“Enter the value to look for: “);
Chapter 12: Recursion 241
case 5:
list.print();
break;
default:
System.out.println(“Sorry, invalid choice”);
}
}
// —————————-
// Prints the user’s choices.
// —————————-
public static void printMenu()
{
System.out.println(“\n Menu “);
System.out.println(” ====”);
A List of Employees
The files Employee.java and Payroll.java contain a definition of a simple list of hourly wage employees. An
employee has a name, number of hours worked, and an hourly pay rate. The Payroll class is the list of
employees. Currently there is a method in the class, public void readPayrollInfo(String file), that reads in the
employee information from a file and sets up the employee list. Your job is to add a recursive method that
determines the number of employees who worked overtime (more than 40 hours). The method numOvertime is
already defined. It is the public method that would be used by a program. It calls your method int overtime (int
start) which will do all the work.
1. Complete the overtime method. The parameter start is the index of the first element in the part of the array
2. Complete the test program Overtime.java to test your method. The program currently has code to read in
3. Run the program at least twice using the files payroll. dat and payroll2. dat as input.
// ***************************************************************
// Employee.java
//
// Represents an hourly wage worker.
// ***************************************************************
this.rate = rate;
}
// ————————————————–
// Returns the number of hours worked.
// ————————————————–
public int getHours ()
{
Chapter 12: Recursion 243
// ***************************************************************
// Payroll.java
//
// Represents a list of employees.
// ***************************************************************
import java.util.Scanner;
import java.util.*;
import java.io.*;
public class Payroll
{
final int MAX =30;
Employee[] payroll = new Employee[MAX];
int numEmployees = 0;
// ———————————————————-
// Reads the list of employee wage data from the given
{
line = fileScan.nextLine();
lineScan = new Scanner(line);
name = lineScan.next ();
try
{
hours = lineScan.nextInt();
rate = lineScan.nextDouble();
244 Chapter 12: Recursion
{
System.out.println (“The file ” + file + ” was not found.”);
}
catch (IOException exception)
{
System.out.println (exception);
}
}
// —————————————–
// Returns the number of employees who
private int overtime (int start)
{
}
}
// ***************************************************************
// Overtime.java
//
// Reads a file of employee payroll information and determines
// how many employees worked more than 40 hours.
// Print the number of workers who worked overtime.
}
}
payroll.dat
Smith 45 13.50
Jones 39 23.75
Summers 40 20.00
Winter 40 18.75
Farthington 38 24.50
Walsh 42 45.70
payroll2.dat
246 Chapter 12: Recursion
Sierpinski Triangles
A Sierpinski triangle is a geometric figure that may be constructed as follows:
1. Draw a triangle.
3. Repeat (2) for each of the outside triangles (not the center one). Each of them will split into four yet smaller
triangles. Repeat for each of their outside triangles.. and for each of the new ones.. and so on, forever. Draw
a few rounds of this on paper to see how it works. Check out the demo at
http://cs.roanoke.edu/labs4e/demo.html to see how the program works on screen.
Your job is to write an applet that draws a Sierpinski triangle. Think about the following:
the x coordinates, an array containing the y coordinates, and an integer indicating how many points should
be drawn (3 for a triangle). Refer to Chapter 7 or the appendix (the Graphics class) to refresh your memory
on this.
Your initial triangle should look like the one in the demo—one point at the top center of the applet and one
point in each lower corner.
guidelines above). For fun you can choose a random color each time as well, as the demo does.
Chapter 12: Recursion 247
Modifying the Koch Snowflake
The Koch snowflake is a fractal generated by starting with 3 line sements forming an equilateral triangle
(a Koch fractal of order 1). The algorithm for generating higher order Koch fractals involves splitting each line
segment into three equal segments then replacing the middle segment by two line segments that protrude
outward. The same algorithm is then recursively applied to each of the 4 new line segments. In the basic Koch
the program in the appletviewer to see how it works (you may use the file Koch.html to run the program). In this
exercise you will generalize the pattern to allow for triangles other than equilateral ones to be built on the
middle third segment. In the drawFractal method this involves changing the calculation of x3 and y3, the
coordinates of the protrusion point. The following calculations are equivalent to those currently in the program:
where cosine is the cosine of 60 degrees (which is 1/2) and sine is the sine of 60 degrees (which is the square
root of 3 over 2). These equations are generalizable to angles other than 60. In this exercise you will generalize
the program to work for angles other than 60. The angle will be controlled by increase and decrease buttons in
1. In KochPanel.java,
Add instance variables angle, sine, and cosine. Angle will be an integer and sine and cosine type
2. Compile and run the program. It should behave just as before.
3. To add controls to allow the angle to change, do the following:
In KochPanel, add two public methods getAngle() that returns the angle (type int), and setAngle (int
newAngle) that sets the angle to be the value of newAngle and sets sine and cosine of that angle.
to 480.
The method actionPerformed must be modified to take action if the event source was one of the new
4. Compile and run the program. Play with the angles and order to see what fractal patterns are generated.
248 Chapter 12: Recursion
// ******************************************************************
// KochSnowflake.java Author: Lewis/Loftus
//
// Demonstrates the use of recursion in graphics.
private KochPanel drawing;
private JPanel appletPanel, tools;
// ——————————————————–
// Sets up the components for the applet.
// ——————————————————–
increase.addActionListener (this);
decrease = new JButton (“Decrease”);
decrease.setMargin (new Insets (0, 0, 0, 0));
decrease.addActionListener (this);
orderLabel = new JLabel (“Order: 1”);
appletPanel. add (drawing);
Chapter 12: Recursion 249
getContentPane().add (appletPanel);
setSize (APPLET_WIDTH, APPLET_HEIGHT);
}
// ————————————————————-
{
orderLabel.setText (“Order: ” + order);
drawing.setOrder (order);
repaint();
}
}
}
250 Chapter 12: Recursion
// *******************************************************************
private final int LEFTX = 60, LEFTY = 300;
private final int RIGHTX = 340, RIGHTY = 300;
private int current; // current order
// —————————————————————–
// Sets the initial fractal order to the value specified.
// —————————————————————–
public void drawFractal (int order, int x1, int y1, int x5, int y5,
Graphics page)
{
int deltaX, deltaY, x2, y2, x3, y3, x4, y4;
if (order ==1)
drawFractal (order – 1, x1, y1, x2, y2, page);
Chapter 12: Recursion 251
drawFractal (order – 1, x2, y2, x3, y3, page);
drawFractal (order – 1, x3, y3, x4, y4, page);
drawFractal (order – 1, x4, y4, x5, y5, page);
}
}
// Sets the fractal order to the specified value.
// ————————————————————–
public void setOrder (int order)
{
current = order;
}
}
koch.html
<html>