## CSE 131 Module 2: Recursion

### Divide and Conquer

In the provided file `LineTool.java`, complete the methods `drawLine` and `drawDashedLine` to recursively draw a line with the given end points. Do not add a Line object to the display. Instead, color individual pixels in the image provided as a parameter. To do this, call the `setPixel` method of the image. For example, if the variable `image` refers to an Image object, the line
` image.setPixel(x, y, Color.RED);`
would replace the color in pixel (x,y) by red.

The `drawLine` method should draw a solid line. The `drawDashedLine` method should draw a segmented (dashed) line, where the lengths of the solid parts and the spaces are approximately equal to the parameter that is passed in. You don't need to be exact, but at least stay within a factor of 2 of the parameter value. Boh methods must be recursive.

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.

To test, run the LineTool.java file as an application. Use the mouse to draw a line in the panel (press to start the line and release to end the line). After you let go, you'll see your the result of your method in the place of the line you drew with the mouse. If you select "Toggle Dash" from the Methods menu, `drawDashedLine` method will be called instead of `drawLine` until the method is toggled again. The parameter value for the dash length is set by choosing the "Set Dash Length" method from the Methods menu. Values are capped between 1 and 100. Values at the low end of the range will be more pleasing.

During testing, after you've drawn several lines, you may want to clear away the clutter by selecting the "Clear" method from the NIP method menu.

### Recursive Patterns

Recursive algorithms can create interesting graphics patterns. Implement recursive solutions to both of the following specifications. Write your methods in the provided file `PatternTool.java`. You may need to write helper methods that perform the actual computation.
1. Pattern 1. Recursive "Flower": This method (`makeFlower`) should call a recursive helper method to add ellipses to a GraphicsPanel to create a flower-like image, as shown in the left image below. The method should have a `void` return type because it only adds shapes to the panel; it does not return a value. As you create each ellipse, fill it with a random color. For your convenience, we have provided a method called `randomColor` that takes no parameters and returns a random translucent color.

If `panel` is the name of your GraphicsPanel parameter, you can add an ellipse to the panel with the statement ```panel.add(new Ellipse(x, y, width, height, color, true);```
where `(x,y)` is the upper left left corner of the bounding box around the ellipse, the next two parameters are the width and height of the ellipse, the color is the desired color of the ellipse, and the last parameter (true) indicates that the ellipse should be filled. (The "bounding box" of a shape is the smallest rectangle that will fit around that shape.)

Your initial call to the recursive helper method will create the largest ellipse, using the dimensions of the entire graphics panel. In other words, you can use (0,0) as the upper left corner and you can use the GraphicsPanel's getWidth() and getHeight() to determine the size of the region for the initial call. After creating the ellipse for the given region, your helper method should make five recursive calls, each for smaller regions within the bounding box of the ellipse you created. The area for the region of each recursive call should be 1/4 of the total area of the bounding box, so we'll call them quadrants. For one region, use a quadrant at the center of the bounding box. For the other four regions, use quadrants whose outside edges are centered along each edge of the bounding box, as shown in the five diagrams below. (Note that the five regions will overlap to create the "flower" effect.) The recursive method shouldn't do anything if the size of the region is too small (say, 10 pixels or less in width or height).

• You may find that your image is rather dark. This is because shapes are added front to back on the panel, so your largest ellipse is on top. Try reordering the statements in your recursive method so that you add the ellipse to the panel after making the five recursive calls. Then the largest ellipse will be at the back.
• To fill an ellipse e, you have to do the following:
• e.setFilled(true);
• e.setFillColor(c);
where c is the color for filling the ellipse. If you fail to set the fill color, it will be the background and it won't look filled.

 Recursive "Flower" Persian Recursion

2. Pattern 2. Persian Recursion: The `makePersian` method should recursively color the pixels of an Image to create the effect of a Persian rug, as shown in the right image above.
Warning: Almost all attempts at this problem that fail are due to incorrect calculations of where to draw the rectangles. Your professor and TAs strongly encourage you to do a few examples on paper to make sure the calculations of the rectangle locations are correct. Be prepared to show them this kind of prototyping exercise when you have questions.
Begin by creating a ColorPalette (see below) and filling the entire image with color 0 (zero) from the palette. Each recursive call will work on a region of the image, where the first call is for the entire image. If the region is at least two pixels wide by two pixels hight, the recursive method should do three things:
1. Choose a color as a function of the colors at the corners.
2. Using that color, draw two lines (a vertical line that is two pixels wide, and a horizontal line that is two pixels high) that cross at the center of the image. Look at the documentation for the method `fillRegion`, which can be called on an Image object to fill a rectangular region of the image with a given color.
3. Make four recursive calls on the uppper-left, upper-right, lower-left, and lower-right quadrants of the image. Be careful about the sizes and corner coordinates of quadrants. For example, if you are dividing a 16 by 16 region, the upper left quadrant's x and y values will range from 0 to 7, and the lower right quadrant's x and y values will range from 8 to 15.

The provided ColorPalette class will be used to keep track of the different colors for your rug. When you create an instance of a ColorPalette, you will pass to the constructor the desired number of colors. (A number between 10 and 50 is reasonable.) To choose the next color to use at each recursive call, use the indexOfColor and colorAtIndex methods of the ColorPalette class. More specifically, you should first use the `getPixelColor(x,y)` method of the Image to find the colors at each of the four corners of the quadrant you are subdividing. Then use the indexOfColor method of your ColorPalette object to get the color numbers that correspond to each of those four colors. So, you'll have four integers, one for each corner. Invent a function that combines those integers to produce another color number. For example, you might add the four numbers, then add some other constant, like 5, and then multiply the whole thing by some other number, like 247. To make sure that you have a color number in the right range, mod (`%`) the result by the number of colors you are using in your color palette. Recall that the `a % b` computes the remainder of `a` divided by `b`, so in the end you'll have a color number that is in the right range (0 to n-1), with n being the number of colors. When you paint the image, you'll need the Color object that corresponds to the color number you computed. You can get this by calling the `colorAtIndex` method of the ColorPalette object.

The particular function you invent is somewhat arbitrary, but different functions will result in different rug designs. To avoid "ugly" designs, you do want to ensure that (1) the function is symmetric... that is, if you swap the colors at any two corners, your function should still compute the same number, and (2) if the corner colors all happen to be the same (which will be the case at the beginning) then your function shouldn't return that same color back, or else you'll get stuck at that one color.

Once your implementation is working, try creating a rug with more detail by increasing the size of the NIP image panels given in the parameters to the constructor in `main`. Use a power of 2. For example, you might try a 512 by 512 rug.)

Footnote: This idea comes from the article "Persian Recursion" by Anne M. Burns that appeared on pages 196-199 of Mathematics Magazine, volume 7, in 1997.