How can I use recursion function for coin change?

Question

I try to use recursion function in Python. I have a scenario in which I live in some country that has 5 and 7 coins. I imagine to go shopping and get to remainder of coins. And I try it from 24 to 1000 and I want to learn that:

• for 24: [5,5,7,7]
• for 25: [5,5,5,5,5]
• for 26: [5,7,7,7]
• .
• .
• .

I get error: 'TypeError: 'int' object is not iterable'

Do you help me about my problem?

amount = range(24,1000)
def change(amount):
    for i in amount:
        for s in range(1,100):
            for j in range(1,100):
                if i == (5*s + 7*j):
                    list = [s,j]
                    print(list)
                else:
                    coins = change(i - 5)
                    coins.append(5)

change(amount)

Answer 1

Thanks to everybody who answered my question. I considered all answers and reorganizes the my codes, like below:

These code snippets run according to the number entered.

def change(amount):
    assert(amount>=24)
    if amount == 24:
        return [5,5,7,7]
    if amount == 25:
        return [5,5,5,5,5]
    if amount == 26:
        return [5,7,7,7]
    if amount == 27:
        return [5,5,5,5,7]
    if amount == 28:
        return [7,7,7,7]
    if amount == 29:
        return [5,5,5,7,7]
    if amount == 30:
        return [5,5,5,5,5,5]

    coins = change(amount -7)
    coins.append(7)
    print (coins)
    return coins

change(100)

Output:

[5, 5, 5, 5, 5, 5, 7]
[5, 5, 5, 5, 5, 5, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7, 7, 7]
[5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

Answer 2

First off, the reason for your error is that you're calling change with two different types of arguments: in your "test case" (the last line) you call it with a range, whereas when you recurse you call it with an int; ranges are iterable, but ints are not iterable.

However, I think you would be well-served by rethinking the algorithm as a whole. Usually, recursion will have fewer loops than an equivalent non-recursive algorithm. For example, these two algorithms both print out numbers from 1 to x, but the second one doesn't have a loop:

def nonrecursive(x):
    for i in range(1, x+1):
        print(i)

def recursive(x):
    if x > 1:
        recursive(x-1)
    print(x)

Recursion can be helpful when you can write the answer to the problem in terms of an answer to a simpler problem. The recursive function keeps trying to solve "simpler" problems until it has to solve an easy problem.

Thus, there are typically two parts to a recursive function: there's one or more recursive cases, which turns one problem into another one, and there's usually at one or more base cases, which are usually the "smallest" problem our algorithm solves.

So, what's the base case in this problem? I would say the base case is 0 — the way to make change for 0 is with no coins: [].

Now what's the recursive case? I would say there are actually two — if you have a solution change(x), then a solution for change(x+5) is the same solution with one more 5 coin; similarly, a solution for change(x+7) is the same solution with one more 7 coin.

Now see if you can piece this together into a complete solution. As a hint, you won't need any for or while loops.

Answer 3

Reason for Error: This change function is taking amount is a integer input. In the first line of this change body we have for i in amount. This for loop is expecting the amount to be either list or tuple or dict or iterator.

This is why you have 'TypeError: 'int' object is not iterable' Error

I recommend the answer provided by user @rhurwitz is really good and would recommend you to look at my reference book - https://runestone.academy/runestone/books/published/pythonds/Recursion/WhatIsRecursion.html to understand recursion well.

Answer 4

For this solution, the key insight is that every amount can be represented as either one of the reference coin sets or as one of the reference coins sets plus a certain number of filler coins. For example, if the amount is 42, that can be represented as 28 + 7 + 7 or as 27 + 5 + 5 + 5.

Note: reference amounts need to be consecutive integers starting from 24 and going up to 30 to allow for filler coins to be of value 7. This is one of the tricky parts. ;^)

Solution:

def coin_count(amount, filler_coin_value=5):
    reference = {
        24: (7, 7, 5, 5), 
        25: (5, 5, 5, 5, 5),
        26: (7, 7, 7, 5), 
        27: (5, 5, 5, 5, 7), 
        28: (7, 7, 7, 7),
        29: (7, 7, 5, 5, 5),
        30: (5, 5, 5, 5, 5, 5)
    }
    coins = []
    while not amount in reference:
        amount -= filler_coin_value
        coins.append(filler_coin_value)
    coins.extend(reference[amount])
    
    return coins

While the above solution works, it can optimized by replacing the the while loop with some (admittedly tricky) math.

def coin_count_optimized(amount, filler_coin_value=5):
    reference = {
        24: (7, 7, 5, 5), 
        25: (5, 5, 5, 5, 5),
        26: (7, 7, 7, 5), 
        27: (5, 5, 5, 5, 7), 
        28: (7, 7, 7, 7),
        29: (7, 7, 5, 5, 5),
        30: (5, 5, 5, 5, 5, 5)
    }
    filler_count, off_by = divmod((amount - 24), filler_coin_value)
    coins = [filler_coin_value] * filler_count
    coins.extend(reference[24 + off_by])
    
    return coins

Time comparison of the two methods:

import time

start_time = time.time()
for amount in range(24, 1000):
    coin_count(amount)
print("coin_count", time.time() - start_time)

start_time = time.time()
for amount in range(24, 1000):
    coin_count_optimized(amount)
print("coin_count_optimized", time.time() - start_time)

Output:

coin_count 0.022232770919799805
coin_count_optimized 0.0019953250885009766

Answer 5

Code can be like as below :

def change(start, end):

    for i in range(start, end):

        ...

change(24,1000)