Lab 11: Recursion

Due 11:59pm Tuesday, November 22, 2011

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 graphics library.

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

1. Recursive Towers of Hanoi
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, ..., followed by the smallest on top). The goal is to move the tower 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 that count the number of minimum number of steps needed to solve the Towers of Hanoi problem. Both functions solve the same problem, but one uses an iterative algorithm while the other uses recursion. Both functions take as a parameter the number of disks to move and both return the minimum number of steps it takes to solve a Towers of Hanoi puzzle for the given number of disks. NOTE: you are not solving the actual problem, but rather counting the steps needed to solve the problem. Section 13.4.1 of the book has a description of the actual Towers of Hanoi problem.

Your main program should:

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)


2. Create a random fractal terrain map

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 one-dimensional terrain map (think of a mountain ridge line).

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

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.

Requirements and Details:

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:

Hints and Tips

Here is the output from two runs of a working program, the first one the user enters 4 for the level value, the second one the user enters 8 (yours 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):



3. Fractal Pattern of Squares

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

  1. create a square graphics window (e.g., 500 by 500) and set the background to black.
  2. prompt the user to enter a depth value.
  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 spliting the window into 9 even sub-squares. The center square will be filled with the passed in 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:

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 the function needs to determine if it needs to make further recursive calls or stop the recursion, and what it needs to know to draw a square to the graphics window at the appropriate position of the appropriate size of the appropriate color.

HINT #1: you should worry about picking colors after you figure out your recursion. You can start off by drawing all squares the same color, like blue.

HINT #2: work on the base case first. Next, figure out how to match the examples at level 1 and level 3. You can first try recurisively drawing just one of the eight smaller square's contents, for example the one to the right. Once you have that working, then add in code to recursively draw each of the eight sub-squares.

Extra Challange Problems
As always, this is not required and should only be attempted once the regular three parts are working correctly. The first suggested challenge problem is mostly for fun, the second problem, however, is more difficult than the required three, and thus more of a challenge, and the third even more challanging still.

1. Cooler than Squares

You could add an extension to the fractal squares problem to draw a more complicated shape than a square each time. 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 want to try out a more interesting shape, cp 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.

2. Koch curves

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 puting 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.


Submit

Once you are satisfied with your programs you can hand them in by typing handin21 in a terminal window. Remember, there are three seperate files to hand-in this week.