CS 151: Lab 11

Title image Project 11
Spring 2020

Lab Exercise 11: Design Exercise

The final project is to use your drawing system to design and create more images. One of the images needs to include a visual element created using recursion.

In a more normal semester, we would be using a 3D turtle package that lets you draw 3D shapes and rotate the scenes after drawing. You are welcome to use the 3D turtle and update your drawing system accordingly. The instructions on the link provide a step-by-step process for doing that.

The default project is to design and create three new images using the drawing system you completed in project 10. If you choose to implement the 3D turtle, you need to create only a single scene based on 2-3 3D shapes. In either case, your scene(s) should include a recursive element.

Video: Recursion Overview


Tasks

The only new concept for this project is creating a recursive visual element. The following walks through how you might go about that within the context of the drawing system from project 10.

Video: Recursive Shapes

  1. Setup

    Create a new folder for the final project (project11). You will be using the lsystem.py, turtle_interpreter.py, tree.py, and shapes.py files from project 10. If you stick to 2D drawing, there are no modifications required to do the rest of the project.

    Start a new file rscene.py. Import shapes.

    To make your life easier, add the following method to your Shape class so you can use a shape to call the TurtleInterpreter hold method. The code assumes you imported turtle_interpreter as ti. Adjust so it works with your code.

        def hold(self):
            ti.TurtleInterpreter().hold()
    						
  2. Thinking Recursively

    Recursion occurs when a function calls itself. A proper recursive function requires two things.

    1. There has to be a termination condition when the recursion stops.
    2. The recursive process must make progress towards the termination condition.

    If either condition is broken, then the recursive process will not stop.

  3. Drawing Recursively: a stack of blocks

    Drawing a recursive shape involves drawing multiple elements and then stopping. While it is possible to draw multiple elements using iteration (in fact, we can do anything with iteration that we do with recursion, and vice-versa) there are some shapes that are much easier to express using recursion.

    Imagine drawing a stack of blocks on top of one another, where each block is 4/5 the size of the block below it. Whatever size we draw the first block at, we want to stop drawing when the size of the block is smaller than 20 pixels on a side. How do we express this recursively?

    First, what is our stopping condition? Given the problem statement, the termination condition is when the size of the block to be drawn is under 20 pixels. This suggests we can use a scale value as a parameter to the recursion function and test it for our termination condition.

    Second, how do we make progress towards the goal? Given the problem statement, each time the recursive function calls itself, it should multply the scale factor by 0.8, or 4/5.

    1. Define a function.
      def drawStack( element, x, y, scale ):

      The first argument is the shape to be draw, x and y define where to draw it, and scale is the scale factor.

    2. Implement the termination condition.

      If the scale factor is less than 20, return.

    3. Draw the shape element.

      Use the element object to call its draw function. Pass in x, y, and scale as the arguments.

    4. Make the recursive call to the next block.

      Call the drawStack function. The first argument should be the element. Then we need to pass in a new x, a new y, and a new scale factor.

      The block on top of this one will be 80% as big. To keep the blocks centered, we need to shift the x position of the next block to the right by 10% of the scale factor. For the second argument, use the expression x + scale*0.1.

      The block on top also needs to be shifted up relative to the current block. If you defined a square using 'F+F+F+F+', then you need to shift up by the size of the current block: y + scale. if you defined a square using 'F-F-F-F-', then you need to shift up by the size of the next block: y + scale*0.8. Choose which expression you need for the third argument.

      The block on top needs to be 80% of the size of the current block. For the fourth argument using scale*0.8. Because we are reducing the size of scale every time we make a recursive call, we are making progress towards the termination condition.

    5. The recursive call finishes the drawStack function.

  4. Make a scene

    The following code makes a square object and calls the recursive drawStack function.

    def main():
    
        s = shapes.Square( distance=1, color='purple' )
        s.setWidth( 3 )
        s.setStyle( 'jitter' )
        s.setJitter( 3 )
    
        drawStack( s, -50, -150, 100)
    
        s.hold()
    
    
    if __name__ == "__main__":
        main()

    Run the code and see what happens. Then edit the code to create two more stacks to the left and right. You can make them a different color by using the s.setColor() function before calling drawStack again. What happens if you use a Triangle instead of a Square shape?

  5. Drawing Recursively: a tree of blocks

    Imagine a block with two smaller blocks on top, each of which has two smaller blocks on top, repeated until the blocks get too small, such as the image below.

    Creating this shape recursively is much easier to design than using iteration. We can think of the shape as a block with a smaller left tree drawn above and to the left, and a smaller right tree drawn above and to the right. The recursive block function only needs to draw itself and then recursively call the tree function to generate the rest of the left tree and again to generate the rest of the right tree.

    1. Define a function.
      def tree( element, x, y, scale ):

      The first argument is the shape to draw, x and y is the location to draw it, and scale is the scale factor to use.

    2. Implement the termination condition.

      If the scale factor is less than 10, return.

    3. Draw the shape element.

      Use the element object to call its draw function. Pass in x, y, and scale as the arguments.

    4. Make the recursive call to draw the left tree on top.

      Call the tree function. The first argument should be element. Then we need to pass in a new x, a new y, and a new scale factor.

      The left block on top of this one will be 50% as big. To put a little space between the blocks, we want to shift it about 40% of scale to the left. For the second argument, use the expression x - 0.4*scale.

      The left block also needs to be shifted up relative to the current block. If you used + to define your square, then shift up by the size of the current block: y + scale. If you used - to define your square, then shift up by half the scale: y + 0.5*scale. Choose which expression you need for the third argument.

      The next block in the tree should be half the size of the current block. Pass in scale*0.5 as the final argument.

    5. Make the recursive call to draw the right tree on top.

      The only difference between the two recursive calls is that the right tree needs to shift to the right instead the left. Use x + scale*0.9 for the second argument.

    Change your call to drawStack in the main function to call tree instead. Mess around with the parameters to see how it affects the tree. Drawing this kind of shape is much more difficult to draw using iteration.


When you are done with the lab exercises you, may begin the project.