**fractal.py**: *20 points*

Fractals are an amazing visual representation of recursion because they are composed of repeating patterns. In this section of the lab, you will write a program called `fractal.py`

that generates two classic fractal patterns. In a `main()`

function, your program should prompt the user to pick a pattern, pick a size, and pick a depth of recursion. The patterns available to the user should be Carpet and Snowflake (more details below). Loops may not be used. To summarize, your program should do the following:

- Print a numbered list of available patterns, and ask the user to select one.
- Get a
`size`

and`depth`

from the user. - Draw the selected pattern on a
`size`

-by-`size`

canvas.

ReadMe

As has been the case all semester, your program should use the `picture.py`

module (docs) and **not** the `turtle`

module.

In the sections below, you will find more information about the different fractal patterns that you will need to generate. You will also find an example of a third “Bubble” fractal. You should use this example to help you get started on your other patterns.

Consider the following sequence of fractal patterns (which are only an example—*you do not need to implement this in your program*):

Each pattern is built entirely out of filled circles. Notice how the pattern changes as the depth increases. The pattern can be described recursively as a single filled circle, with four patterns of one lesser `depth`

and half the `size`

, offset to the northwest, northeast, southwest, and southeast.

For this fractal, the repeating function is drawing a circle, then repeating four times around the just-drawn circle. This implies that the design of the recursion is to draw a circle at a given center `(x,y)`

and with a given radius `r`

, then make four recursive calls with:

- new centers (one recursive call for each of the northwest, northeast, southwest, and southeast),
- half the radius of the just-drawn circle,
- one less depth (so we count down to depth == 0).

This process continues `depth`

times. So a simple base case is to check the value of `depth`

: if it is greater than 0, keep drawing, else stop (by returning from the function).

The code used to implement this fractal is provided for you in `bubbles.py`

. Run the program and try to understand how it works. Please feel free to use this example to help you with the following fractals.

The Carpet pattern, also known as Sierpinski’s Carpet, is built entirely out of filled squares. The pattern can be described recursively as a single filled square (whose sides are one third the width of the region containing the square), with eight patterns of one lesser depth and one third the size, offset to the north, northeast, east, southeast, south, southwest, west, and northwest. See the examples below.

At this point we’re ready to define our recurrence more precisely. When designing recursive algorithms, it’s critical that you think about how your recurrence works not just at the top level, but also at subsequent levels. It’s easy to define a recurrence that does what you intend on the first step, or even the first few steps, but then breaks down on deeper iterations.

In this case, it’s tempting to simply say that the largest square is drawn centered halfway from top to bottom and side to side, and the next recursive calls are made centered at 1/6 width by 1/6 height (for the northwest repeat), 1/2 width and 1/6 height (for the north repeat), etc. Unfortunately, that description doesn’t lend itself to a useful recurrence. What happens now when the lower-right subproblem is solved recursively?

To deal with this, we need a more general description. In particular, try to figure out what it would mean to draw this pattern with depth `d`

, centered at position `(x,y)`

, with a size of `r`

(just like our Bubble fractal example above). Note that you shouldn’t assume `x`

and `y`

correspond to the middle of the canvas, because in many recursive calls they won’t. Similarly, don’t assume that `r`

is at all related to `x`

or `y`

. It might be helpful to work through the details of this recurrence on paper.

Now create a function called `carpet()`

in your `fractal.py`

program that generates this pattern. You’ll need to decide upon a few things. In particular, what parameters will this function take in? And what will the initial call to this function look like? If something goes wrong, find the smallest depth at which things break down and trace through what your program is doing. You may find you’ve implemented your design incorrectly, or you may need to revisit the algorithm itself. Along the way, make sure to comment your code.

The Snowflake, also known as Koch’s Snowflake, is a fractal made from line segments.

To understand the Snowflake design, let’s think about drawing only one of the three sides of the Snowflake (for example, focus on the bottom side of the Depth 1 Snowflake above). When `depth == 1`

, the side is just a line. For higher depths, the side is made up of several lines. What does this hint about the base case of the recursion?

For `depth == 2`

, the side is no longer a single line, but four line segments—each with one third the length of the line at `depth == 1`

and some angles between those lines. Altogether, these four line segments replace one edge of the triangle from `depth == 1`

. For `depth == 3`

, each line in `depth == 2`

is replaced with the same pattern, just as the line from `depth == 1`

was replaced to create `depth == 2`

. This hints that the recursion involves drawing four lines with angle rotations between them.

Once we understand the recursion for each side of the snowflake, then the only thing left to do is to draw all three sides of the fractal. Unlike the other fractal patterns, the recursive function doesn’t draw the entire snowflake, but only one side. So instead we need three total calls to the `snowflake()`

function in our `main`

function (one call for each side). Remember that you’ll have to rotate the pen after each call to `snowflake()`

in order to draw each side.

Now create a function called `snowflake()`

that generates one edge of the Snowflake pattern. *What parameters does it require?* Below are some picture functions you may find useful for this pattern.

`picture.rotate(theta)`

- rotate pen`theta`

degrees clockwise (note that`theta`

can be positive or negative)`picture.draw_forward(d)`

- draw a length-`d`

line from the current position in the current direction`picture.set_position(x,y)`

- move the pen to position`(x,y)`

You are required to draw your snowflake such that, for any depth `d`

, it is fully visible (i.e. nothing drawn outside the canvas!). You are welcome to center your snowflake, but that is not a requirement.