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
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:
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 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.
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
from graphics import * from random import *
xA = 0.1*width xB = 0.9*width yA = height/2 yB = height/2
changeX = distance between xA and xB rangeY = changeX/4+1You 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.
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):
You will implement a program, fractalsquares.py that recursively draws a pattern of squares to the graphics window. Your program will:
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.
$ 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 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:
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.
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.