The goal of this lab is to learn about recursion. You will write three programs that make calls to recursive functions. Some of these are based on producing fractal patterns and will use the Zelle graphics library.

To start, run update21 to create the cs21/labs/11 directory.

The Towers of Hanoi is a puzzle consisting of three pegs and some number of disks, each with a different diameter. At the start of the game, the disks are arranged on peg 1 as a tower (the largest disk on the bottom, followed by the second largest, and so on with the smallest on top). The goal is to move the tower of disks to the third peg. At each step only a single disk can be moved from one peg to another, and at no point can a larger disk cover a smaller disk. The wikipedia page for towers of hanoi explains more about the puzzle.

In a file named towersofhanoi.py you will implement two versions of a function (one recursive, one iterative) that takes the number of disks and returns the minimum number of steps it takes to solve a Towers of Hanoi puzzle for the given number of disks. Both functions solve the same problem, but one uses an iterative algorithm while the other uses recursion. Also note, you are not solving the actual puzzle, only counting the steps needed to solve the puzzle. Section 13.4.1 of the book has a description of the actual Towers of Hanoi problem.

Your main program should:

• Get the number of disks in the tower from the user.
• Call your iterative function to calculate the number of steps.
• Print the results of your iterative function.
• Call your recursive function to calculate the number of steps.
• Print the results of your recursive function.

The number of steps to solve a puzzle with N disks is defined by the following recursive definition:

1. a 1 disk puzzle takes 1 step (move the disk from peg 1 to peg 3)
2. a puzzle of N disks takes 1 plus 2 times the number of steps it takes to solve the puzzle with N-1 disks

Thus,

 for 1 disk it takes 1 step
 for 2 disks it takes 1 + 2 times the number of steps to solve for 1 disk =  3 
 for 3 disks it takes 1 + 2 times the number of steps to solve for 2 disks = 7 
 for 4 disks it takes 1 + 2 times the number of steps to solve for 3 disks = 15 
 ...

Here are some sample runs of a working program:

$ python towersofhanoi.py
This program computes the minimum number of steps it takes
to solve a Towers of Hanoi puzzle of a given number of disks.
Enter the number of disks in the puzzle: 3
For a Towers of Hanoi puzzle of size 3 it takes:
        7 steps (iteratively)
        7 steps (recursively)

$ python towersofhanoi.py
This program computes the minimum number of steps it takes
to solve a Towers of Hanoi puzzle of a given number of disks.
Enter the number of disks in the puzzle: 5
For a Towers of Hanoi puzzle of size 5 it takes:
        31 steps (iteratively)
        31 steps (recursively)

$ python towersofhanoi.py
This program computes the minimum number of steps it takes
to solve a Towers of Hanoi puzzle of a given number of disks.
Enter the number of disks in the puzzle: 10
For a Towers of Hanoi puzzle of size 10 it takes:
        1023 steps (iteratively)
        1023 steps (recursively)

Recursion can be used in graphics to produce realistic natural images, such as ferns, trees, and terrain. For this program you will use the midpoint displacement algorithm to create a realistic random one-dimensional (1D) terrain map (think of a mountain ridge line).

The midpoint displacement algorithm, using recursion, is as follows:

• start with two points A and B
• if the recursive level is 0, just draw the line from point A to point B
• if the recursive level is greater than 0, find the midpoint C, displace it vertically a small random amount, then recur twice using points A-C and points C-B
• each time the function recurs, the level should decrease by one

Here are four examples of 1D terrains for recursive depths 0 (the straight line) to 3:

Note: in the above sample images, I drew the midpoints to help you understand the problem. Your program does not need to draw dots at each midpoint. Also, to get the midpoint x and y coordinates between two points A and B, use the following:

           midx = (Ax + Bx) * 0.5
           midy = (Ay + By) * 0.5

In a file named terrain.py, write a program to create a one-dimensional terrain map, using a recursion depth given by the user. Your program should:

• ask the user for the recursion depth
• open a graphics window that is wider than tall (700x400 works well)
• call a recursive function to create and draw the terrain
• use random vertical midpoint displacements that look realistic and get smaller as your program recurs
• wait for a mouse click before closing the window

Remember that to use the graphics and random libraries, your program needs to import them:

from graphics import *
from random import *

Here is output from two runs of a working program. In the first one the user entered 5 for the recursive level. In the second one the user entered 8 (your terrains will not be identical to these, due to the random change in y value at each step, but the amount of detail should be similar):

You will implement a program, fractalsquares.py that recursively draws a pattern of squares to the graphics window. Your program will:

1. prompt the user to enter a depth value.
2. create a square graphics window.
3. call your recursive drawsquares function to recursively draw a fractal pattern of squares for the given depth of recursion.
4. wait for the user to click in the graphics window to exit.

For example, here are the results of two runs of a working program, the first is for a level 1 pattern, the second for a level 3 pattern:

This pattern is based on recursively splitting the window into 9 even sub-squares. The center square will be filled with the given color. The other 8 should be recursively filled with squares of dimension one third of the current square's size.

Your recursive squares function should do the following:

1. create, draw, and color a square of given size at a given point
2. if the depth level is greater than zero, think of the current drawing space as divided into 9 equal sub-squares, and make eight recursive calls to draw smaller squares to the eight sub-squares (above right, above, above left, left, right, below right, below, below left) at the next smallest depth level
3. Each of the eight recursive calls should draw a square of a different color. Use colorPicker to find colors in the graphics library.

For this problem, we are leaving it up to you to figure out what you need to pass to your recursive function at each step. Think about what data the function requires to determine if it needs to make further recursive calls or stop the recursion. Also, what does the function need in order to draw a square to the graphics window with the appropriate position, size, and color?

As always, these are not required and should only be attempted once the above parts are working correctly. The first suggested challenge problem is mostly for fun. The second and third problems, however, are more difficult than the others, and thus more of a challenge.

1. Cooler than Squares

Add an extension to the fractal squares problem to draw a more complicated shape than a square. For example, if you draw the square and then draw four smaller black squares in each corner, you could draw a plus sign at each step. If you do this, copy your fractlsquares.py file to fractalextra.py and add the more interesting shape in this file:

$ cp fractalsquares.py fractalextra.py
$ vim fractalextra.py

You could also play around with the colors, too. Here are some additional ideas to try...

2. Koch curves

(see Turtle graphics NOTE and example at the end of this lab for help with this program)

Below are examples of six Koch curves that have recursion depths from 0 (a straight line) at the top to 5 at the bottom.

A Koch curve is created by breaking a line segment into thirds and replacing the middle segment by two segments that are equal in length. This creates a two-sided equilateral triangle in the middle (e.g., all angles are 60 degrees).

You should start by creating a program called koch.py. You will write a function:

drawKochCurve(win, n, start, end, angle)

which draws a Koch curve from point start to a point end with recursion depth n where angle specifies the angle of the line that connects start to end.

A Koch curve of recursion depth n is formed by four Koch curves as follows:

1. drawing a Koch curve of length length/3 with degree n-1 and angle
2. drawing a Koch curve of length length/3 with degree n-1 and angle-radians(60)
3. drawing a Koch curve of length length/3 with degree n-1 and angle+radians(60)
4. drawing a Koch curve of length length/3 with degree n-1 and angle

Hint: Each one of these recursive calls is starting from a different starting point.

3. Koch snowflake

Once you have successfully created a single Koch curve, you can try putting three Koch curves together to create a Koch snowflake (cp your koch.py to kochsnowflake.py). The snowflake shown below is an example of a Koch snowflake made with 3 Koch curves.

NOTE: the Koch curves are much easier to do using the python Turtle graphics package. Each "turtle" has a position, a direction, and a pen. Drawing consists of moving and turning the "turtle". Here is a simple program that shows how to use Turtle graphics in python:

import turtle

def main():
  w = 400
  h = 400
  turtle.setup(width=w, height=h)

  # create a turtle (named bob)
  bob = turtle.Turtle()
  bob.color("black")
  bob.forward(100)
  bob.left(90)
  bob.forward(100)
  bob.right(90)
  bob.forward(100)

  turtle.exitonclick()

main()

Once you are satisfied with your programs you can hand them in by typing handin21 in a terminal window.

Last updated: Tuesday, September 22, 2020 at 12:25:26 PM