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:
depthfrom the user.
As has been the case all semester, your program should use the
picture.py module (docs) and not the
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:
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
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
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?
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
thetadegrees clockwise (note that
thetacan be positive or negative)
picture.draw_forward(d)- draw a length-
dline from the current position in the current direction
picture.set_position(x,y)- move the pen to position
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.