Outline for March 9, 2012

1. Recursion review
2. Example: binary search [rbinsearch.py]
   1. Base case: high < low, return failure; word == list[mid], return mid
   2. Recursive part: if word < list[mid], search interval 0 ... mid-1; if word > list[mid], search interval mid+1 ... high
3. Example: Tower of Hanoi [hanoi.py]
   1. The story
   2. Base case: 1 disk, just move it
   3. Recursive part: move n−1 disks to second pole, move bottom disk to third, move disks on second pole to third
   4. Show stack for 3 disks
4. Example: reverse string [reverse.py]
   1. Base case: empty string
   2. Recursive part: reverse(s): reverse(s[1:]) + s[0]

ECS 10, Basic Concepts of Computing Winter Quarter 2012