A set of coins makes change for n if the sum of the values of the coins is n. For example, if you have 1-cent, 2-cent and 4-cent coins, the following sets make change for 7:

• 7 1-cent coins
• 5 1-cent, 1 2-cent coins
• 3 1-cent, 2 2-cent coins
• 3 1-cent, 1 4-cent coins
• 1 1-cent, 3 2-cent coins
• 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for 7. This function count_changetakes a positive integer n and a list of the coin denominations and returns the number of ways to make change for n using these coins (Hint: You will need to use tree recursion):

def count_change(amount, denominations):

  """Returns the number of ways to make change for amount.

  >>> denominations = [50, 25, 10, 5, 1]

  >>> count_change(7, denominations)

  2

  >>> count_change(100, denominations)

  292

  >>> denominations = [16, 8, 4, 2, 1]

  >>> count_change(7, denominations)

  6

  >>> count_change(10, denominations)

  14

  >>> count_change(20, denominations)

  60

  """

  "*** YOUR CODE HERE ***"  

  def count_using(min_coin, amount):

    if amount < 0:

      return 0

    elif amount == 0:

      return 1

    elif min_coin > amount:

      return 0

    else:

      with_min = count_using(min_coin, amount - min_coin)

      without_min = count_using(2*min_coin, amount)

      return with_min + without_min

  return count_using(1, amount)