Recursive Exercises

For the exercises below, first try using paper, pencil, discussion, thinking, and acting out to solve them before using the Python Interpreter to check your answers.

Merge Sort

Stand up! Act out the following algorithm that sorts items by dividing a given list of data in halves, then combining those smaller lists back together in sorted order. Thus, a list of a single element is considered sorted, a list of two elements is the combination of two one-element lists in sorted order, a list of four elements is created by combining two two-element lists in sorted order, and on and on until the entire list is in sorted order.

def mergeSort (data):
    if len(data) == 1:
        return data
    else:
        middleIdx = len(data)/2
        leftHalf = mergeSort(data[:middleIdx]) 
        rightHalf = mergeSort(data[middleIdx:])
        return combine(leftHalf, rightHalf)
  

Here it is acted out as a dance.

Tower of Hanoi

Write a pseudocode algorithm to the Tower of Hanoi game discussed in class, given

• a number of disks in the tower (an int greater than 0)
• the starting tower (a string like 'A')
• the ending tower (a string like 'C')
• the intermediate tower (a string like 'B')

Determine how many moves it will take to solve the Tower of Hanoi game for a given number of disks. To solve this problem, try to determine the exact number of moves needed for several examples with a small number of disks. Once you have calculated several examples, try to find a pattern in how these numbers change for each number of disks.

Making Change

Making change is an important activity that occupies a lot of people's time. Some people have difficulty figuring out how to make their coins add up to the right amount; while others have problems figuring out how to make a given sum from what they have in their pocket.

Describe a recursive algorithm to solve the problem of using the fewest coins to represent a given amount of money. You can assume you are using standard American coins (pennies, dimes, nickels, and quarters) and that you have an "infinite" number of any given coin (i.e., you will not run out of any kind of coins while making change).

For example, if asked to change seventy-six cents, your algorithm should list: 3 quarters, 1 penny. If asked to change ten cents, your algorithm should list: 1 dime.