teaching machines

CS 245 Lecture 12 – Recursion

February 27, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

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