Recursive coin change (partitions) with powers of 2

Question

Question: Count_Change

Once the machines take over, the denomination of every coin will be a power of two: 1-cent, 2-cent, 4-cent, 8-cent, 16-cent, etc. There will be no limit to how much a coin can be worth.

Given a positive integer amount, a set of coins makes change for amount if the sum of the values of the coins is amount. For example, 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. Write a recursive function count_change that takes a positive integer amount and returns the number of ways to make change for amount using these coins of the future.

Sample Run；

def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_change', ['While', 'For'])
    True

My code:

def largestPart(k):
        if k <= 1:
            return 0
        else:
            i = 1
            while i < k:
                i = 2 * i
        return i
    def partFunction(n,m):
        if n <= 0:
            return 0
        elif m <= 0:
            return 0
        elif n == 1:
            return 1
        elif m == 1:
            return 1
        return partFunction(n - m, m) + partFunction(n, m // 2)
    return partFunction(amount, largestPart(amount))

My Question: When the input value n is equal to 10, the returned value suppose to be 14, but I kept getting 10 as the returned value. Can anybody tell me why I got 10? Any help is really appreciated!

Answer 1

If n equals zero, partFunction should return 1.