def change(amount, Coins):
    '''Returns the smallest number of coins from Coins that add up to
    amount.  If no combination of coins from Coins add up to amount,
    returns infinity.
    '''
    if amount == 0:
        return 0
    if Coins == []:
        return float('inf')
    It = Coins[0]
    if It > amount:
        return change(amount, Coins[1:])
    useIt = 1 + change(amount - It, Coins)
    loseIt = change(amount, Coins[1:])
    return min(useIt, loseIt)

def insert(x, sortedList):
    '''Takes a number and sorted list as input and returns a new list
    that has x inserted into the right place in the sorted list.
    '''
    if sortedList == []:
        return [x]
    elif x <= sortedList[0]:
        return [x] + sortedList
    else:
        return [sortedList[0]] + insert(x, sortedList[1:])

def sort(L):
    if L == []:
        return []
    else:
        return insert(L[0], sort(L[1:]))

def mergesort(myList):
    '''Mergesort the given list
    '''
    if len(myList) <= 1:
        return myList
    return merge(mergesort(myList[0:len(myList) // 2]),
                 mergesort(myList[len(myList) // 2:]))

def merge(sortedList1, sortedList2):
    '''Merge two sorted arrays
    '''
    if sortedList1 == []:
        return sortedList2
    if sortedList2 == []:
        return sortedList1
    if sortedList2[0] < sortedList1[0]:
        return [sortedList2[0]] + merge(sortedList1, sortedList2[1:])
    return [sortedList1[0]] + merge(sortedList1[1:], sortedList2)

# Dictionaries

def translate():
    D = {"hello":"hola", "goodbye":"adios", "good":"bueno", "spam":"spam"}
    for word in D:
        print(word, "is:", D[word])
    D["more"] = "mas"

letter_values = {
    'e': 1, 'a': 1, 'i': 1, 'o': 1, 'n': 1, 'r': 1, 't': 1, 'l': 1, 's': 1, 'u': 1,
    'd': 2, 'g': 2,
    'b': 3, 'c': 3, 'm': 3, 'p': 3,
    'f': 4, 'h': 4, 'v': 4, 'w': 4, 'y': 4,
    'k': 5,
    'j': 8, 'x': 8,
    'q': 10, 'z': 10
}
    
def score(myString, letter_values):
    if myString == '':
        return 0
    return letter_values[myString[0]] + score(myString[1:], letter_values)

def score_iterative(myString, letter_values):
    total = 0
    for letter in myString:
        total += letter_values[letter]
    return total