CS 245 Lecture 12 – Recursion
Agenda
- what ?s
- recursion
- finding a file
- binary search
- concentric circles
- terrain generation
- merge sort
TODO
- I updated the HW2 PDF. Go to Bitbucket and sync with my repository. Pull the changes down in Eclipse.
- Start homework 2. Due before 3/14.
Code
FindFile.java
package lecture12;
import java.io.File;
public class FindFile {
public static void main(String[] args) {
find("grades.csv", new File("/Users/johnch"));
}
private static void find(String name, File root) {
if (name.equals(root.getName())) {
System.out.println(root.getPath());
} else {
File[] children = root.listFiles();
if (children != null) {
for (File child : children) {
find(name, child);
}
}
}
}
}
TerrainGenerator.java
package lecture12;
import java.awt.Color;
import java.awt.Graphics;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class TerrainGenerator extends JFrame {
private double[] heights;
public TerrainGenerator() {
add(new TerrainPanel());
heights = new double[1024 + 1];
Random g = new Random();
heights[0] = g.nextDouble() * 600;
heights[heights.length - 1] = g.nextDouble() * 600;
perturb(0, heights.length - 1, g, 1.0);
setDefaultCloseOperation(EXIT_ON_CLOSE);
setSize(1024, 600);
setVisible(true);
}
private void perturb(int lo, int hi, Random g, double decay) {
if (lo + 1 == hi) {
// there is no midpoint
return;
}
// find midpoint
int mid = (lo + hi) / 2;
// set midpoint's elevation to average of lo and hi points
heights[mid] = (heights[lo] + heights[hi]) / 2.0;
heights[mid] += (g.nextDouble() - 0.5) * 200 * decay;
// descend
perturb(lo, mid, g, decay / 2.0);
perturb(mid, hi, g, decay / 1.1);
}
private class TerrainPanel extends JPanel {
@Override
public void paintComponent(Graphics g) {
g.setColor(Color.GREEN);
for (int i = 0; i < heights.length - 1; ++i) {
g.drawLine(i, (int) heights[i], i + 1, (int) heights[i + 1]);
}
}
}
public static void main(String[] args) {
new TerrainGenerator();
}
}
ArrayUtilities.java
package lecture12;
public class ArrayUtilities {
public static int indexOf(int[] numbers,
int target) {
int first = 0;
int last = numbers.length - 1;
while (first <= last) {
int mid = (last + first) / 2;
if (numbers[mid] > target) {
last = mid - 1;
} else if (numbers[mid] < target) {
first = mid + 1;
} else {
return mid;
}
}
return -1;
}
public static int indexOfRecursive(int[] numbers,
int target,
int first,
int last) {
if (numbers == null) {
throw new RuntimeException("why why why?");
}
// Window has become inverted. Let's throw in the towel.
if (first > last) {
return -1;
}
int mid = (last + first) / 2;
if (numbers[mid] > target) {
return indexOfRecursive(numbers, target, first, mid - 1);
} else if (numbers[mid] < target) {
return indexOfRecursive(numbers, target, mid + 1, last);
} else {
return mid;
}
}
public static void main(String[] args) {
int[] numbers = {
42, 54, 93, 103, 100000
};
System.out.println(indexOf(numbers, 42));
}
}
Target.java
package lecture12;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class Target extends JFrame implements MouseMotionListener {
private Point mouseLastAt = new Point(0, 0);
public Target() {
JPanel panel = new TargetPanel();
add(panel);
panel.addMouseMotionListener(this);
setDefaultCloseOperation(EXIT_ON_CLOSE);
setSize(1024, 600);
setVisible(true);
}
private class TargetPanel extends JPanel {
@Override
public void paintComponent(Graphics g) {
drawCircles(g, 500);
}
}
private void drawCircles(Graphics g,
int radius) {
if (radius >= 5) {
// draw a red circle
g.setColor(Color.RED);
g.fillOval(mouseLastAt.x - radius, mouseLastAt.y - radius, radius * 2, radius * 2);
// draw a smaller white circle
g.setColor(Color.WHITE);
radius -= 5;
g.fillOval(mouseLastAt.x - radius, mouseLastAt.y - radius, radius * 2, radius * 2);
// draw inner circles
drawCircles(g, radius - 5);
}
}
public static void main(String[] args) {
new Target();
}
@Override
public void mouseDragged(MouseEvent arg0) {
}
@Override
public void mouseMoved(MouseEvent event) {
mouseLastAt = event.getPoint();
repaint();
}
}
Haiku
I batted Mom’s smoke
“A million likes and I’ll quit”
Hours later: air
“A million likes and I’ll quit”
Hours later: air