Matthew L. Wright
Assistant Professor, St. Olaf College

# Homework 18: Recursion

## CS 121 ⋅ Spring 2016

The following exercises involve recursion. Upload the your solutions to Moodle for HW18.

1. Write a recursive function that prints the sequence of moves necessary to solve the Tower of Hanoi problem.

Specifically, your program should first ask the user for a number of disks, and then print the sequence of moves required to move the stack of disks from post 1 to post 3. Recall that only one disk may be moved at a time, and a large disk may not be placed on top of a smaller disk. Assume disk 1 is smaller than disk 2, which is smaller than disk 3, and so on.

For example, the Python console might look something like this when you run your program:

``` How many disks? 2 Move disk 1 from post 1 to post 2 Move disk 2 from post 1 to post 3 Move disk 1 from post 2 to post 3 DONE ```
2. Write a function that implements the binary search algorithm to search for an item in a sorted list.

`def binarySearch(alist, item):`

This function requires that the list alist be sorted in ascending order. The function returns True if item is in the list alist, and False otherwise.

Recall the binary search algorithm from class:

• If the list is empty, then return False.
• Otherwise, look at the middle item in the list; if that is the desired item, then return True.
• Otherwise, recursively search either the left half or the right half of the list, depending on whether the desired item is greater than or less than the middle item of the current list.

You must write a recursive algorithm to receive full credit.