Due 11:59pm Saturday, 7 December 2013

Run `update21` to create the
`cs21/labs/10` directory containing the starting files for this lab
Then cd into your `cs21/labs/10`
directory and create the python programs for lab 10 in this directory
(handin21 looks for your lab 10 assignments in your `cs21/labs/10` directory).

$ update21 $ cd cs21/labs/10

For this lab, you will write a few small recursive programs.

1. Recursive Towers of Hanoi

The
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. As a reminder, you are not *solving* the actual puzzle,
only counting the steps needed to solve the puzzle.

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:

- 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)

You may notice that the solution is described by a simple closed form formula 2**n-1, but you should not use this formula directly in your program. Since we are practicing iteration version recursion, your solutions should use these features.

2. Palindromes

A palindrome is a word or phrase in which the sequence of letters in the phrase is identical if read forwards or backwards. Examples include "kayak", "Rats live on no evil star", "A Toyota's a Toyota", and "A man, a plan, a canal: Panama". Note that spacing and punctuation are ignored when determining if a phrase is a palindrome.
Write a recursive function $ python palindrome.py Enter a phrase: kayak 'kayak' is a palindrome $ python palindrome.py Enter a phrase: puppy 'puppy' is not a palindrome $ python palindrome.py Enter a phrase: madam, I'm Adam 'madam, I'm Adam' is a palindrome

3. Insert Pattern

In the file pattern.py, write a print insertPattern("puppies", "*") p*u*p*p*i*e*s print insertPattern("pumpkin pie", "-") p-u-m-p-k-i-n- -p-i-e print insertPattern("yolo", "at") yatoatlatoYour function should have the same behavior as

4. Is Sorted

In the file sorted.py, write a recursive function called print isSorted([1, 2, 4, 5 , 8]) print isSorted([1, 12, 4, 5 , 8]) print isSorted(["apple", "cranberry", "pumpkin", "turkey"]) empty = [] print isSorted(empty) output: True False True True

5. Recursive drawing

In `triangle.py`, write a recursive function:

fracTriangle(window, top, left, right, color, n)that takes as parameters a GraphWin

The base case: n = 0

Recall that every recursive function needs a base case where the
recursion ends. For your `fracTriangle` function, the base
case should occur when `n` is zero; your `fracTriangle`
function should use `top`, `left`, and `right` to draw
a single triangle of the given color, and then return.
For example, with `color`=`"white"` and `n`=0, your
function should produce something like the single triangle below.
Your image should not contain the text labels "top", "left", and "right".
We just put them in the image to clarify how the triangle is drawn.

The recursive case: n > 0

If `n` is greater than zero, your function should use `top`,
`left`, and `right` to draw a
triangle of the appropriate color (same as before) and
** then use three recursive calls (with depth n-1)
to draw smaller triangles inside the given triangle**.
The three recursive
calls should draw triangles of the

- top, midLeft, and midRight
- midLeft, left, and midBottom
- midRight, midBottom, and right

Note: given two points (graphics Point objects!), like top and right, you can calculate and create a new midpoint like this:

midx = (top.getX() + right.getX()) * 0.5 midy = (top.getY() + right.getY()) * 0.5 midright = Point(midx, midy)You could even write a function (hint, hint!) to return a midpoint, given two starting points. :)

For reference, the diagram below was produced with depth `n`=1 and
`color`=`"white"` (again, your program shouldn't label the points).
Note how the center area (marked here in French) is white from the
first call to `fracTriangle`, and the three black triangles
(from the 3 recursive calls to `fracTriangle`) are drawn on
top of the original white triangle.

Here are a few more examples.
The left image below was drawn with `n` = 2 and
`color` = `"white"`, and the right image was drawn with
`n` = 3 and `color` = `"white"`:

Using larger depths can lead to attractive patterns, but can take a long
time! The following diagram was drawn with `color`=`"white"` and
`n`=7:

The main function

In `main()`, your program should read in a recursive depth
`n` and initial color (`"black"` or `"white"`)
and draw the pattern of the appropriate recursive depth.

To summarize, here are some hints for the recursion:

- For the base case (when
`n`equals 0),`fracTriangle`should draw a single triangle and make no recursive calls. - For non-base cases,
`fracTriangle`should draw a single triangle and make three recursive calls. Each recursive call should:- correspond to one of the triangles (using midLeft, midRight, and midBottom) described above.
- reverse the color.
- use a recursion depth that is one smaller than the current recursion depth.

- Your
`main`function should call`fracTriangle`just once. All other triangles should be drawn using recursive calls.

Submit

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