CS 101 Laboratory #8
Recursion

Objective: To gain experience designing recursive methods.

Due date is the beginning of your lab section next week:

Lab prep: Review the slides from Lectures 20 and 21, and the examples from Lecture 21.

Written Exercises

None this week.

Lab Exercises

Note: Exercises 2-5 use Turtle graphics, as discussed in Class 21. Here is a contract for the Turtle Class. Create a hw08 directory in your cs101 directory, and save Turtle.class and TurtleWorld.class to it.

  1. Earlier this semester we studied Euclid's algorithm for computing the greatest common divisor of two integers. Review your notes from Class 12 on this algorithm. Then write a class GCD.java that implements Euclid's algorithm using a recursive method. Turn in a printout of your source code, as well as sample output showing that your code works correctly.

  2. Save the SquareWorld.java and SquareTurtle.java files into your hw08 directory. For this exercise, you will not need to modify SquareWorld.java.

    A SquareTurtle is a kind of Turtle that can draw squares as well as staircases made up of squares. Before making any changes, compile and run SquareWorld.java (it will automatically compile SquareTurtle.java, too). Click on the "run" button, and notice what the turtle draws. Now modify the drawHalfSquare method in SquareTurtle.java so that a SquareTurtle correctly draws a square (by drawing two half squares). Then modify the drawStaircase method so that it recursively draws pictures such as the one to the right. Employ the following strategy: (1) draw a square, (2) pick up the pen and move to a new location, (3) put down the pen, and then (4) recursively draw the rest of the squares. Turn in a printout of your final SquareTurtle.java file, as well as a screen snapshot showing that your code works correctly. You can create a snapshot of part of the screen with Apple-Shift-4.

  3. Now modify your code from question 2, saving to a new file named SquareTurtle2.java. This time, produce the same picture, but without retracing and without picking up the pen. You should modify SquareWorld.java so that it uses a SquareTurtle2 object rather than a SquareTurtle object. Turn in a printout of your SquareTurtle2.java file, as well as a screen snapshot showing that your code works correctly.

  4. Sierpinski's gasket is a self-similar triangular entity named after its discoverer. In this problem we will write a recursive method to approximate Sierpinski's gasket. Let sierpinski(sideLength, levels) be the notation for a Sierpinski gasket with levels levels and side length sideLength. Then a recursive mathematical definition of sierpinski is as follows:

    The pictures below depict sierpinski(sideLength, levels) for levels = 1 through 5.

    sierpinski(100,1)

    sierpinski(100,2)

    sierpinski(100,3)

    sierpinski(100,4)

    sierpinski(100,5)

    Save the SierpinskiWorld.java file into your hw08 directory. Modify SierpinskiWorld.java and create a new SierpinskiTurtle.java file so that when you run SierpinskiWorld (not SierpinskiTurtle), it draws Sierpinski's gasket as described above. Turn in a printout of both files, as well as screen snapshots showing that your code works correctly for at least two different levels values.

  5. Extra credit: Use Turtle graphics to draw the recursive leaf shown here (inspired by the recursive leaf applet shown in Class 20). FYI, to help with choosing values for constants, this picture was generated with the following settings:
    1. base case stops drawing if the stem length ≤ .2
    2. the next leaf to the front is .9*stemLength, to the right by 3 degrees
    3. the leaf on the left is .28*stemLength, to the left by 60 degrees
    4. the leaf on the right is .33*stemLength, to the right by 55 degrees, drawn one-third of the way up the stem
    Extra extra credit: Notice that the leaves on this image curl both up and down, while the leaves in the fractal applet all curve up. Find an elegant way to revise your code so that all the leaves curl up as in the fractal applet (here is an example picture). Turn in a printout of your source code, as well as screen snapshots showing that your code works correctly.

  6. About how long did it take you to complete this assignment?

Back to Computer Science 101 Home
Department of Computer Science