Warmup

Part A: Recursion by Hand

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

1. What is the output of print(strange(3))?

def weird(x):
    if x > 0:
        print(x)
        if x%2 == 0:
            weird(x-3)
            weird(x-2)
        else:
            weird(x-1)

2. What is the output of weird(8)?

3. Only when you have fully attempted both exercises by hand, you should run the file weirdlystrange.py to check your answers.

Part B: Recursion with Strings

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 recursive_reverse(s).

message = 'hello!'
message[1:]   #returns 'ello!'
message[-1]   #returns '!'
message[1:-1] #returns 'ello'

Part C: Fractal Images

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.

Sierpinski Carpet

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?

Write your answers in WARMUP.md. Knowing these locations will be helpful when you work on Part 3 of the lab.

Koch Snowflake

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?

Again, record your answers in WARMUP.md. Knowing these angles will be helpful when you work on Part 3 of the lab.