Problem 4: Count change (200pts)

Denomination is a proper description of a currency amount, usually for coins or banknotes. For example, we have 1 Yuan coins and 100 Yuan bills in Chinese Yuan.

A money function is a function which takes a positive integer representing a denomination and returns the next larger denomination of the input or None if there is no larger denomination. Its behavior is undefined if the input is not a valid denomination.

Money function can be used to describe a currency system. For example, the following money function describes Chinese Yuan (1 Yuan, 5 Yuan, 10 Yuan, 20 Yuan, 50 Yuan and 100 Yuan). You can assume the smallest denomination of all currencies is always 1.

def chinese_yuan(money):
    if money == 1:
        return 5
    if money == 5:
        return 10
    if money == 10:
        return 20
    if money == 20:
        return 50
    if money == 50:
        return 100 

Given an amount of money total and a currency system, a set of banknotes (coins) makes change for total if sum of their values is exactly total. For example, the following sets make change for 15 Chinese Yuan:

• 15 1-Yuan
• 10 1-Yuan, 1 5-Yuan
• 5 1-Yuan, 2 5-Yuan
• 5 1-Yuan, 1 10-Yuan
• 3 5-Yuan
• 1 5-Yuan, 1 10-Yuan

Thus, there are 6 different ways to make change for 15 Chinese Yuan.

Write a recursive function count_change that takes a positive integer total and a money function next_money and returns the number of ways to make change for total under the currency system described by next_money.

Hint: Refer the implementation of count_partitions for an example of how to count the ways to sum up to a total with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.

def count_change(total, next_money):
    """Return the number of ways to make change for total,
    under the currency system described by next_money.

    >>> def chinese_yuan(money):
    ...     if money == 1:
    ...         return 5
    ...     if money == 5:
    ...         return 10
    ...     if money == 10:
    ...         return 20
    ...     if money == 20:
    ...         return 50
    ...     if money == 50:
    ...         return 100
    >>> def us_cent(money):
    ...     if money == 1:
    ...         return 5
    ...     elif money == 5:
    ...         return 10
    ...     elif money == 10:
    ...         return 25
    >>> count_change(15, chinese_yuan)
    6
    >>> count_change(49, chinese_yuan)
    44
    >>> count_change(49, us_cent)
    39
    >>> count_change(49, lambda x: x * 2)
    692
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_change', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"