15-110
Spring 2011
Recitation 9
- No quiz this
week
- Review
- Recursion
Review: More
general recursive reverse
The recursion notes
include this solution to reverse:
def
reverse(s):
if (s == ""):
return ""
else:
return reverse(s[1:]) + s[0]
print
reverse("abcd")
This works for strings, but not for lists. In particular, see
what happens if you try this:
print reverse([2, 3, 5, 7])
- Explain exactly what went wrong.
- Modify the implementation of reverse so that it works
equally well for lists as well as strings.
- Even this modified version has some problems.
For example, reverse(range(1000)) fails. Why?
- The same notes include an iterative version of
reverse() right next to the recursive version. Modify this
iterative version so that it also works over lists, and try to
reverse(range(1000)). It works now. Why?
- Recursion +
Graphics Review: Sierpinski's
Triangle
Write a Tkinter program that waits for the user to
press a key, and if the key is a digit, the program draws a Sierpinski
Triangle up to the given depth. Here are Sierpinski Triangles
at increasing depths:
As close inspection should reveal, to draw a Sierpinski Triangle of
depth 0, just draw a black triangle, whereas at higher depths, split
the triangle into 3 pieces (by connecting the midpoints of the edges),
and recursively draw Sierpinski Triangles in each smaller triangle.
Thought
question: this works very well for depths 0, 1, 2, ... but fails
after depth 8 or so. Describe the visual symptom of failure, and
then the underlying cause.
- Animations
Review: Simple
Invaders Game
Some (but not all) lectures yesterday wrote this simple invaders game. Review how the code works,
and make some interesting changes to the game as time allows.
- Sample solutions
It's probably best not to review these prior to your recitation, but here is a solution to the recursive reverse problem and to the Sierpinski Triangle problem. Enjoy!
- Return
midterm1