Lab 4: Recursion and Fractals with Turtle Graphics

If you find typos or problems with the lab instructions, please let us know.

Goals

This includes writing parameterized functions, developing test code and solving problems using recursion. You’ll do some warm up recursive programs, predict and test what they do, and then top it all off by creating some very cool fractal art.

Your learning goals are:

• Determine the base case and recursive step in a recursive solution.

• Implement this recursive solution in Python.

• Learn to reason about your program, and justify its correctness.

• Find and fix errors in simple Python functions.

• Trace the value of variables in Python code.

• Reason about the quality and completeness of test cases.

• Use geometry and turtle graphics to draw fractals in Python.

Work Flow

For each of the programming exercises in this lab, come up with a solution outline by discussing with your partner. Don’t be in a hurry to start coding unless you have a fairly clear idea of a solution strategy. Only when you have come up with a clear strategy, start the coding process. Test your code constantly, maybe starting with simple cases first. Make sure to commit your code frequently. Push working versions of your code to github.

Developing code is an iterative process. Your code will probably not work as expected on the very first try. Don’t be dismayed. Work through your code to identify bugs, test new code frequently and seek help if you feel you are stuck!

Setting up your repo

Create a new shared Repl for this lab assignment from these instructions, as you did in lab0. There is no starter code in this lab. The name of your repo should be spis20-lab04-Name1-Name2, just like we've done in previous labs.

Programming Exercises

Let’s begin with our very first exercise which is a warmup on recursion.

Multiply without the ‘*’ operator

We’re going to write a recursive function that multiplies two integers without using the * (multiplication) operator, only + (addition). Your program should work for positive and negative values of ‘a’ and ‘b’. For now, let’s consider the case where ‘b’ takes only non-negative values and ‘a’ may be positive, negative or zero. Recognize that:

a * b = a + a + a + … + a (with b copies of a added together)

E.g.,

3 * 4 = 3 + 3 + 3 + 3

In other words, we want to define a function rec_product(a, b) which will have integers as arguments and will return the product of its arguments. But, the function shouldn’t use the operation *.

Just for practice, take a minute to (a) determine the base case and (b) write the recursive step without looking below. After you’ve got it, read on. If you don’t know where to start, please ask for help. Scroll down when you have an answer.

Your base case probably looks something like:

a * 0 = 0

That is, when b is 0, then the product of 0 times any number is 0.

Your recursive step should be something like:

a * b = a + a * (b - 1)

In your Repl project, create a new file recursive_prod.py. Your task is to complete the function below, which implements recursive multiplication.

def rec_product(a, b):

'''Calculate product a * b recursively'''

When you are done, test your code. For example, check that your program does the following:

rec_product(0, 5) returns 0

rec_product(1, 5) returns 5

rec_product(-1, 5) returns -5

If any of your test cases fail, it means either there is an error in your code or your code doesn’t cover that particular case and you need to write additional code. You have to re-examine your code and figure out what is wrong. This process is known as debugging.

Once you have tested your code for the cases where the parameter b is non-negative, while the parameter a is any integer that maybe positive, negative or zero, try changing your code to handle when b is negative. Any ideas? Once you think you've got it, test the previous cases again and a few additional cases where the parameters b is negative. Here are a few example cases where b is negative:

rec_product(5, -1) should return -5

rec_product(-5, -1) should return 5

If your code passes these cases, great! If not implement the logic needed to handle the case where b is negative. After you are done, consider refactoring your code to arrive at an elegant and concise solution.

Recursive Rendering

It is time for you to start showing off your skills visually. You will do this by writing programs to create cool fractal art, which is based on internal self-similarity.

We’ll start by creating two classical fractals: a spiral and a tree. Then you get to try your hand at creating snowflakes.

The Python Turtle Library

You’ve already started playing with Python’s Turtle library in the previous lab. For more information on the turtle library refer to the documentation on the turtle library.

In your Repl project, create 3 files called recursive_spiral.py, recursive_tree.py, and recursive_snowflake.py and put all your upcoming code in the appropriate file. Remember, we need to import the turtle library to use the turtle package (all of the turtle functions), so include this at the top of your files:

import turtle

Important: You might have to run your turtle code several times to see the output, because there is some serious lag with Turtle Graphics and Repl.it's output window. You can get rid of the lag by doing this: create a new Repl.it, choose "Python (with Turtle)" as the language, and write your code in there. However, make sure to copy and paste this code into your normal Repl.it though, so that you can push it to Github! The reason that we don't use "Python (with Turtle)" as the normal language for Turtle Graphics labs is because "Python (with Turtle)" only allows 1 file per Repl.it, so we cannot connect it to the Github repo!

Drawing a Spiral

In the file recursive_spiral.py create the spiral function which has the following signature.

spiral(initial_length, angle, multiplier)

The function takes as arguments an initial_length of the spiral’s first line segment, an angle specifying the degree of the angle formed by neighboring segments, and a multiplier indicating how each segment changes in size from the previous one. For example, the following are example screenshots from different spiral calls:

Notice that the angle is specified in degrees.

In the first call the fractal starts from the center with initial_length 100 pixels. It turns right by 90 degrees when it needs to draw a successive segment whose length is 0.9 times that of the previous one. In the second one, the fractal starts from the center with initial_length 1 pixel. Each iteration the line turns left by 45 degree and draw a segment whose length is 1.1 times longer.

Note the spiral function can be computed inside-out, or outside-in, depending on the multiplier, therefore the base case varies. The spiral should stop drawing when it has reached a side length of less than 1 pixel (if multiplier<1) or greater than 200 pixels (if multiplier>1).

Implement the function and use it to draw an interesting spiral of your own.

Help! Stack Overflow! Do not be alarmed if you find you are getting stack overflow errors when you try to run the “growing spiral” example above. This error is caused by an infinite recursion, i.e. a recursion that never hits its base case. Not sure why? This is a perfect time to practice some of those debugging skills you learned above. :) Ask a tutor if you need help.

Useful debugging hint: You can change the speed with which your turtle draws. Assuming your turtle is bob, adding the code bob.speed(1) causes it to move as slow as possible, which can help you figure out what is going on in your algorithm. If you change ‘1’ to higher numbers, your turtle will speed up. However, somewhat counter-intuitively, bob.speed(0) has the turtle move as fast as possible, which is useful when your algorithm is working and you want to try it out with a larger recursion depth.

Growing a Tree

Next, you will write the tree function. In recursive_tree.py, create the tree function with the following signature:

tree(trunk_length, height)

The function takes as arguments: a trunk_length which is the length of the main trunk of the tree, and the height indicating the number of levels of branching of the tree. For example, the following is an example screenshot from the call to tree(200, 4):

The tree “grows” from the ground of the world, with initial length of the first trunk as 200 pixels. At the end of the first segment, the trunk forks into two directions. The forked trunk in each direction has a shorter length and continues to fork at the end, until the tree has forked 4 times.

Think about the base case and its recursive steps before implementing the function.

Your tree will be personalized by the aesthetic choices you make about the number of branches at each fork (anything greater than 1 is OK), the exact angle of branching, the reduction of trunk_length in sub-branches. Your tree is planted on the ground and should grow upward.

Draw some interesting trees using your function.

Creating Snowflakes

By now you should be very skilled at creating fractals using recursions. Congratulations! Now you can do much more, even making it snow during summer in sunny San Diego. In this exercise, you will create the following snowflake structure (a.k.a. Koch Snowflake). Note that your function parameters will determine its size and how many levels to draw in the snowflake:

As the image shows, the Koch snowflake begins with an equilateral triangle; at each level, the middle third of each line segment is replaced by a pair of line segments that can, together with the replaced segment, form an equilateral triangle; then the replacement will be performed again on all the component line segments of the newly created shape, over and over. This is illustrated in the bellow image:

The code to create the Koch Snowflake will be written in recursive_snowflake.py. We will draw the Koch Snowflake by first defining the snowflake function with the following signature:

snowflake(side_length, levels)

which takes as arguments: a side_length of the initial equilateral triangle, and the levels indicating the number of recursive levels performed to create the final snowflake. Observe that the base case is simply an equilateral triangle with side length equal to side_length. Each increment of level replaces the middle third of all of the snowflake’s sides with a “bump” that is, itself, a smaller equilateral triangle.

You might be thinking to yourself, "How can I replace part of the snowflake's sides with a 'bump' (equilateral triangle)? Is there an erase function on turtle I can use?" Well, we won't actually be replacing it! Instead, we're going to use a helper function with the following signature to draw out a single snowflake side (including the necessary 'bumps' for the corresponding snowflake level):

snowflake_side(side_length, levels)

snowflake_side should draw just one side of the underlying equilateral triangle – along with all of its bumps (equilateral triangles) – recursively! Look at these images, which should help you understand what snowflake_side draws for each level:

As you can see, snowflake_side simply draws a single side of the snowflake, with all of the bumps! snowflake then uses snowflake_side three times to draw the whole snowflake! The below image shows that the 3 calls of snowflake_side in snowflake draws exactly what you want, a snowflake:

This means that all of the recursion to draw a single side and its bumps will be in snowflake_side! If levels is zero, then snowflake_side should produce a single line segment of length side_length (this will be the base case of the recursion); otherwise, snowflake_side needs to call itself four times, with appropriate angles between the calls. Think to yourself, why four times? What angles should be used between the calls?

Again, in this strategy, all of the recursion occurs in snowflake_side. So, you should first try creating snowflake_side and make sure that it works and draws a single side of the snowflake at the appropriate level of recursion. Then, once snowflake_side works, have your snowflake function call snowflake_side three times, with appropriate angles between the calls.

Once you think you're implementation is correct, test it by calling snowflake(140, 4); you should get the following snowflake:

If that works, try calling snowflake(140, 4) and then afterwards snowflake(140, 0). Are these snowflakes the same size? If not, then try changing your code so that they would be (hint: the change(s) should be in snowflake_side).

Drawing the snowflake is definitely challenging. If you have completed this exercise consider it a major accomplishment!! Congratulations on working your way through recursion and lab04! However, you may find that you want to hone your recursion skills a little more. So go ahead and try out the challenge problems.

Challenge Problem - Custom Snowflake

Create a new file recursive_custom_snowflake.py. Copy over your code from recursive_snowflake.py, and change it to allow for a custom number of snowflake sides.

Challenge Problem - Sierpinski Triangles

Create a new file recursive_triangles.py. Use recursion to have your turtle create the famous Sierpinski triangles, shown below.

More fractal challenge problems

If you want to go still deeper into fractals and recursion, get creative drawing new fractals. There is a general way to recursively create many types of fractals, called fractal decomposition. One starts with a shape oriented in a space along with a replacement rule which is used to refine the picture. One useful (but optional) rule of thumb is to not remove any shapes once they have been put down, but only to add on to what already exists. Another is to use different replacement rules with various probabilities. Try several of these out, and figure out what kinds of rules lead to beautiful designs. Put all of your code for the optional fractal drawing in a new file called fractal_challenge.py.

A list of famous, and intensively studied, fractals is available here.

Here are some pictures for inspiration:

Additional exercises

As an individual, you could create an art gallery out of the fractals! Consider the fractals you created in this lab and imagine what you could create by making changes to your existing code. Please be sure to name your art gallery fractal files differently from the lab fractal files so that your mentor can review all that you created.

Great job working through lab 4. Feel free to move on to the next lab.