Lab 10: Recursion

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 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. Writing a program to print the list of moves needed to solve the puzzle is a bit complicated, so you will write a simpler program which only counts the minimum number of moves needed to solve the puzzle using a formula given below.

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:

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)

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 palindrome(phrase) in palindrome.py which returns True if the string value phrase is a palindrome and returns False otherwise. Test your function by writing a small main function which asks for a phrase and determines if the phrase is a palindrome. Your function should work for phrases containing punctuation, spaces, and uppercase and lowercase letters. 
$ 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 recursive function called insertPattern(phrase, pattern) which takes a string phrase and a string pattern and inserts the pattern between adjacent characters in the phrase. The function should return a new string containing the modified phrase. Examples are shown below: 
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")
yatoatlato
Your function should have the same behavior as pattern.join(list(phrase)), but you should not use join() or list() in your recursive solution
4. Is Sorted
In the file sorted.py, write a recursive function called isSorted(ls) which determines if the items in ls are sorted in increasing order. Your function should return True if the items are sorted, and False otherwise. Write a small main function to test your solution. Some examples are shown below. 
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 window, three Points (top, left, and right), a color that will be "black" or "white", and an integer n which is the recursive depth. The fracTriangle function should draw a triangle of color color in the graphics window and then, depending on the depth n, either return or recursively use the fracTriangle function to draw smaller triangles as described below.



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 opposite color defined by the points illustrated below:

  1. top, midLeft, and midRight
  2. midLeft, left, and midBottom
  3. 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:

Submit

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