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:

- Get the number of disks in the tower from the user.
- Call your iterative function to get the number of steps.
- Print the results of your iterative function.
- Call your recursive function to get the number of steps to solve the Towers of Hanoi problem.
- 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:

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

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:

- 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 (i.e., the point half-way between A and B). Displace C vertically a small random amount, then recur twice, once using points A-C and the other using 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.

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 the midpoint displacement algorithm above)
- wait for a mouse click before closing the window

**Hints and Tips**

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

- You will need to define values for A and B when making your initial
call to the recursive function. For a window of height
`height`and width`width`, define the x and y values of A and B as follows:xA = 0.1*width xB = 0.9*width yA = height/2 yB = height/2

- When making your two recursive calls, you will need to calculate
the midpoint C that lies half-way between A and B. The y-value of C should
be adjusted some random amount to create a realistic look.
You can use the following formula to calculate the range of adjustment values:
changeX = distance between xA and xB rangeY = changeX/4+1

You should then sample a displacement value randomly between -rangeY and rangeY and add it to the midpoint value. There are other methods for calculating random displacement, so feel free to try something else. Your displacement factor, however, should get smaller as you get into deeper levels of recursion. - Debuging: you can add in calls to sleep(0.05) to slow down the recursion and see what it gets drawn at each step. Adding debug print statements to print out the point (x,y) coordinates at each recursive call may also help. Just remember to remove both debug print statement and debug calls to sleep before your submit your solution.

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:

- create a square graphics window (e.g., 500 by 500) and set the background to black.
- prompt the user to enter a depth value.
- call your recursive drawsquares function to recursively draw a fractal pattern of squares for the given depth of recursion.
- wait for the user to click in the graphics window to exit.

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:

- Divide the current square into 9 smaller squares.
- If the depth level is 0: simply fill in the center square centered at the given point in the graphics window, using the passed in color.
- otherwise, you will make recursive calls. First, fill the center square with the passed in color. The other eight squares will be filled by making recursive calls to draw smaller squares (at the next smallest depth level) based on the sub-square's location and width.
- 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 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.
$ cp fractalsquares.py fractalextra.py $ vim fractalextra.pyYou could also play around with the colors too.

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

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

- drawing a Koch curve of length
`length/3`with degree`n-1`and angle - drawing a Koch curve of length
`length/3`with degree`n-1`and angle-radians(60) - drawing a Koch curve of length
`length/3`with degree`n-1`and angle+radians(60) - 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.

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.