Lab 10: Recursion

Lab note: You will submit no written report for this lab. Instead, after completing each problem, a TA or the instructor will check off that you have completed it. Your grade will be based purely on these visual checks. All problems must be completed by the end of the scheduled lab to get full credit.

Objectives

• to practice writing recursive methods.

Before continuing, execute the following commands to copy your work from Lab 8 to this lab.

% getcs 160 10
% cp ~/CS160/Lab8/*.java ~/CS160/Lab10

Part A. Koch Snowflake

Figure 10.1: The Koch snowflake

Write a program to draw a Koch snowflake, illustrated in Figure 10.1. The Koch snowflake includes three Koch curves arranged in a triangle, each as follows.

You can derive a Koch curve by beginning with the following basic four-segment piece.

For programming, it's more useful to look at the procedure as a recursive one: We observe that a Koch curve includes four smaller Koch curves. Thus, to draw a Koch curve, we draw a shorter Koch curve, then we turn left 60 degrees and draw another Koch curve, then we turn right 120 degrees and draw another Koch curve, and then we turn left 60 degrees and draw a final Koch curve. Figure 10.2 contains pseudocode for this process.¹

procedure drawKochCurve(length):
if length < 1, then:
    Move forward length pixels.
else:
    drawKochCurve(length / 3).
    Turn left 60 degrees.
    drawKochCurve(length / 3).
    Turn right 120 degrees.
    drawKochCurve(length / 3).
    Turn left 60 degrees.
    drawKochCurve(length / 3).
end if

You'll want to use the Pen class of the csbsju.cs160.gui library (available via getPen() from DrawableFrame). I recommend that the pen begin at (25,56.7) and draw each Koch curve with a length of 150.

Part B. Mine Camp, Part II

First, close all open files in the editor. Then, edit the package lines of MineButton.java and MineCamp.java to reflect that you're now working on Lab 10.

If you've solved the puzzle from last lab many times, you know that frequently there are large regions of the grid where no buttons have any mines around them. It's a pain to have to manually explore these, as it's obvious that when you find such a point, you can safely step on all the surrounding points. In this lab, we'll modify the program so that the computer does it for you.

Define a new method in MineCamp.

void step(int i, int j)

Reveals what's under the button at grid point (i,j), and, if the point wasn't mined and hid a count of 0, recursively steps on all hidden surrounding grid points.