CODEWITHSUNDEEP
pythonrecursionoptimization
user4562262
user4562262

Reputation: 170

Minimum number of coins to make up an amount using recursion

The problem is the popular one to illustrate Dynamic Programming, which is as follows. We have unlimited coins of each of the denominations 1, 3, and 5. We want the minimum number of coins to get the amount N.

I am aware of the Dynamic Programming method where we build up a solution from the base case(s). But I wanted to see how to write a purely recursive solution. I am able to work it out easily by hand for N = 11 and denominations = [1,3,5]. But for some reason I am unable to make the following work.

    def minNumberOfCoins(amount, denominations):
        if amount <= 0:
            return(0)
        if amount in denominations:
            return(1)
        else:
            listToExamine = list(filter(lambda x: x > 0, map(lambda x: amount - x, denominations)))
            print(listToExamine)
            minVal = min(listToExamine, key=lambda x: 1 + minNumberOfCoins(x, denominations))
            return(minVal)

As far as I can tell, the logic is identical to what I worked out on paper. Is there some nuance in Python's recursion I am not aware of, or is there something subtle I have been missing? Thank you!

Upvotes: 0

Views: 1619

Answers (2)

user2390182
user2390182

Reputation: 73450

More readable approach. You should not mix map or filter with lambdas so much. Conditional comprehensions and generators are usually the better choice:

def min_coins(amount, denominations):
    # these two base cases seem to cover more edge cases correctly
    if amount < 0:
        return None
    if amount == 0:
        return 0
    tries = (min_coins(amount-d, denominations) for d in denominations)
    try:
        return 1 + min(t for t in tries if t is not None)
    except ValueError:  # the generator in min produces no values
        return None   

min_coins(11, [1,3,5])
# 3

Upvotes: 1

John Gordon
John Gordon

Reputation: 33275

This implementation seems more straightforward:

def minNumberOfCoins(amount, denominations):

    if amount <= 0:
        return(0)

    if amount in denominations:
        return(1)

    for d in sorted(denominations, reverse=True):
        if d <= amount:
            return 1 + minNumberOfCoins(amount - d, denominations)

Upvotes: 1

Related Questions