Tracing a recursive function by hand can be very helpful for understanding the progression of method calls. Examine the following two recursive functions, and attempt to answer the associated questions by tracing the method calls by hand. This is a great time to get out a piece of paper and a writing implement.
def strange(x): if x <= 0: return 1 else: return 5 * strange(x-1) - 2
def weird(x): if x > 0: print(x) if x%2 == 0: weird(x-3) weird(x-2) else: weird(x-1)
Only when you have fully attempted both exercises by hand, you should run the file
weirdlystrange.py to check your answers.
There are many different ways to reverse a string. In the file
gnirts.py, you’ll find a function called
loop_reverse(s) that uses a
for loop to reverse the string
s. You will also find a function called
recursive_reverse(s) that is only partially complete (i.e., only the base case has been written). Work with your partner to write the recursive function call necessary to finish
String slicing will likely help you finish
recursive_reverse(s). As a reminder, here are some examples of string slicing.
message = 'hello!' message[1:] #returns 'ello!' message[-1] #returns '!' message[1:-1] #returns 'ello'
In this lab, you’ll be drawing fractal patterns, like this Sierpinski Carpet below.
This part of the warmup will take you through the some of the math required.
Fractals are images that are self-similar. This can be seen in the Sierpinski Carpet by noticing that it contains eight smaller Sierpinski sub-Carpets, arranged around the center square of the image. Just like
picture.draw_square(x,y,side), you can imagine identifying a sub-carpet’s location with its top left corner. If the canvas has width and height of
size, what are the locations of the points A through I, below?
Knowing these locations will be helpful when you work on Part 3 of the lab.
One of your other fractals will be the Koch Snowflake (shown below).
To draw the Koch Snowflake, you’ll be drawing three copies of the “Koch Curve.”
Notice that this doesn’t involve any shapes. Instead, we’ll be drawing lines using the the pen from the
picture module. Below, you’ll see the simplest non-base-case version of the Koch Curve. Imagine your pen starts at point A, facing right. If the straight-line distance from A to E is
length, each of the four line segments has length
length/3. What angles will you need to rotate at points B, C, and D to draw the curve?
Knowing these angles will be helpful when you work on Part 3 of the lab.