CSE 131 Module 7: Recursion

Divide and Conquer

In the extensions source folder, find and open the lines package and the Lines class contained therein. The main method is provided, and it calls the method drawLine,which you must complete.
Do not change the parameters or return type of the drawLine method! You are welcome to define other methods in the Lines class if you wish, but the drawLine method's signature (the number and types of its parameters and its return type) must be preserved as you do your work.

Your task is to devise an algorithm for drawing a line from (x1,y1) to (x2,y2) using recursion. It may take you some time to think about how to do that, but once you see the recursive nature of drawing a line, you will probably need only a few lines of code to accomplish this task.

Please take note of the following guidelines, as you will not receive credit unless your solution follows the rules of this assignment:

• The code given to you will perform a test of your drawLine when you run it as a Java Application.
• If you want to draw lines interactively using your solution, then run the INteractiveLines class as a Java Application.
• Do not use StdDraw.line to do any of your work!
• The only methods you are allowed to use from StdDraw are point, setPenRadius, and setPenColor.
This means you must draw your line one point at a time.
• Some students approach this problem by computing the slope of the line and then incrementally trying to draw pieces of it using recursion. That approach comes to grief for vertical lines, which have infinite slope. There is a much easier and satisfying way to solve this problem, but you have to think about it.
Do not compute or use the slope of the line in your approach. We will not count the extension if you do that. Instead, think recursively about how a line is constructed.
When you done with this extension, you must be cleared by the TA to receive credit.
• Commit all your work to your repository
• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

 Last name WUSTL Key Propagate? (or your numeric ID) Do not propagate e.g. Smith j.smith 1 Copy from 1 to all others 2 Copy from 2 to all others

TA: Password:

Persian Recursian

The idea for this assignment comes from the article "Persian Recursion" by Anne M. Burns that appeared on pages 196-199 of Mathematics Magazine, volume 7, in 1997.
In the extensions folder open the recursivepatterns package and the PersianRug class. Your task is to complete the method persianRug so that it draws a rug similar to the one shown below:
Each call to persianRug works on a given square of the rug. Consider the picture shown below:
• The square is described by its lower-left corner (in this case, (0,0)), and its size (in this case, 1).
• Each step of the recursion considers the colors of the provided square's sides (in this case, blue), and computes a color for the two lines to be drawn inside the square (in this case, red).
Computing the color of these two lines is what makes the rug look as it does. More detail is given below concerning how to pick a color.
• Further recursion would act on the sub-squares you see in the above picture. For example, the upper-left subsquare has its lower-left corner at (0, 0.5), has size 0.5, and has colors blue, red, red, blue, starting from north and proceeding clockwise.

The parameters for persianRug are documented in the source code provided to you for this extension.

Notes:

• Colors in this lab are represented as an index into a Color array called palette. This array is provided for you in the source code and it is passed into your
• Indexes into palette are passed into persianRug to describe the colors of the square's bordering edges. For example, blue is represented by index 0 into the palette array, and cyan appears at index 1.
• Picking a color for the two lines drawn inside a given square is the creative aspect of this assignment. The following should be read carefully and understood before you jump into coding.
• Although you will eventually pick more diverse colors, we recommend that unti your lab is working, you should always use color index 0 for the color of the two drawn lines.
• Once that is working, you must pick a color that is a function of the square's bordering colors (which are conveniently represented as indexes into palette. That function must have the following properties to perform correctly:
• The function must return a value that is an appropriate index into the palette array.
As you know, 0 is the smallest index, and the largest index is palette.length-1.
• The function must return the same value for any permutation of a given square's bordering colors. For example, if the colors are specified in order red, blue, blue, red, then any square with two blue and two red sides must compute the same color for the two drawn lines.
Recall that these colors are represented as integers, each being an index into the palette array. What kinds of functions on integers return the same result no matter the order of those integers?
• Different functions will produce different rugs. The rug below is computed using the same code as the rug shown at the top of this assignment, but the function was tweaked slightly:
Perhaps you can see that in the above rug, once a square has red on each of its borders, the two drawn lines inside that square are also red. That effect just happens to be a property of the function I used to produce the above image.

• Rugs contributed Fall 2013:
 Ben Greene Dylan Jew and Ari Spilo Alan Waldman Sam Chase Meagan Provencher Ben Zod Diana Fasanello Anna Kolasa and Kunyao Liu
• When things go wrong, it is almost always because you do not have a consistent view of the square as presented to persianRug. Ask for help as needed!
When you done with this extension, you must be cleared by the TA to receive credit.
• Commit all your work to your repository
• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

 Last name WUSTL Key Propagate? (or your numeric ID) Do not propagate e.g. Smith j.smith 1 Copy from 1 to all others 2 Copy from 2 to all others

TA: Password:

Flower Power

In the extensions folder open the recursivepatterns package. The following classes found there, and described in greater detail below, must be completed for this extension:
• TransparentColor
• Flower
The ultimate goal is to complete the flower method of the Flower class so that it draws an image similar to the one shown below:
The colors shown in the above image are somewhat transparent, so that the color of an ellipse is allowed to bleed through the ellipse above it.

You can proceed by working on either class first. However, if you postpone TransparentColor, you will see solid colors in your flower until you have completed that class.

Details

TransparentColor
As is the case with most color models, Java's Color objects are allowed to have a degree of transparency.

The transparentColor method, as provided to you, ignores the alpha parameter and returns the color provided as input.

You must change this behavior so that the color returned as the same red, green, and blue components as the provided color, but with the specified transparency.
Java makes this easy, because there is a constructor for Color that does the job. This task is given to you primarily to acquaint you with the process of looking through JavaDoc documentation to find a class or method you need.

Follow the instructions provided in the TransparentColor source code.

Before moving on, test your code by running TransparentColor as a Java Application. You should see the colors solid at the upper right of the drawing window, and blended (more transparent) at the lower left.

You must demo this to a TA when you seek credit for this extension.

Flower
Your task here is to complete the flower method, whose parameters are described in the JavaDoc for the method. Some useful guildines follow:
• The StdDraw class offers a filledEllipse method, but you must set the color before calling it.
• You should choose a random color for each ellipse you draw, and you are provided a palette of Color objects as input to your flower method.
If necessary, review the material in the text and slides that discusses how to pick a random integer. You would use that integer to index the palette array.
• You must find the substructure in the flower pattern. To help with this, the following diagram shows the locations of each ellipse within a given level of recursion:
• Analyze the above diagrams to infer the area taken up by each sub-ellipse that you must draw.
• Remember that the StdDraw coordinate system has (0,0) at the lower-left, and (1,1) at the upper right.
• Remember that StdDraw shapes take a center as their primary coordinate, and use half-widths and half-lengths for dimensions.
As usual, ask for help as needed.
When you done with this extension, you must be cleared by the TA to receive credit.
• Commit all your work to your repository
• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

 Last name WUSTL Key Propagate? (or your numeric ID) Do not propagate e.g. Smith j.smith 1 Copy from 1 to all others 2 Copy from 2 to all others

TA: Password: