- Recursion review
- Example: binary search
[
*rbinsearch.py*]- Base case:
`high < low`, return failure;`word == list[mid]`, return`mid` - Recursive part: if
`word < list[mid]`, search interval`0 ... mid-1`; if`word > list[mid]`, search interval`mid+1 ... high`

- Base case:
- Example: Tower of Hanoi
[
*hanoi.py*]- The story
- Base case: 1 disk, just move it
- Recursive part: move
*n*−1 disks to second pole, move bottom disk to third, move disks on second pole to third - Show stack for 3 disks

- Example: reverse string
[
*reverse.py*]- Base case: empty string
- Recursive part:
`reverse(s)`:`reverse(s[1:]) + s[0]`

A PDF version is available here.

ECS 10, Basic Concepts of Computing Winter Quarter 2012 |