Matthew L. Wright
Visiting 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.

    Your function header should be:

    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.

  3. Answer the following questions. (You may type your answers in a text file.)
    1. What is the smallest number of moves that will solve the Tower of Hanoi problem for 4 disks?
    2. What is the smallest number of moves that will solve the Tower of Hanoi problem for n disks? (Your answer will be an expression that depends on n.)
    3. Suppose you have a sorted list of 7 items. If you do a binary search on this list, what is the maximum number of items in the list that will need to be examined before the search algorithm can return True or False?
    4. What is the size of the largest list such that a binary search on the list will always return True or False by examining no more than 5 items in the list?