如何使用递归函数进行硬币兑换

首先，错误的原因是您使用两种不同类型的参数调用change：；测试用例"；(最后一行(您用range调用它，而当您递归时，则用int调用它；range是可迭代的，但int是不可迭代的。

然而，我认为重新思考整个算法会对您大有裨益。通常，递归比等效的非递归算法具有更少的循环。例如，这两种算法都打印出从1到x的数字，但第二种算法没有循环：

def nonrecursive(x):
    for i in range(1, x+1):
        print(i)
def recursive(x):
    if x > 1:
        recursive(x-1)
    print(x)

当你可以用简单问题的答案来写问题的答案时，递归会很有帮助。递归函数一直试图解决"；"更简单"；直到它必须解决一个简单的问题。

因此，递归函数通常有两个部分：有一个或多个递归情况，它将一个问题转化为另一个问题，并且通常有一个以上基本情况那么，这个问题的基本情况是什么？我认为基本情况是0——对0进行更改的方法是不使用硬币：[]。

现在递归的情况是什么？我想说实际上有两个——如果你有一个解决方案change(x)，那么change(x+5)的解决方案就是多了一个5硬币的相同解决方案；类似地，change(x+7)的解决方案与多一个7硬币的解决方案相同。

现在看看你是否可以把这些拼凑成一个完整的解决方案。作为提示，您不需要任何for或while循环。

对于这个解决方案，关键的见解是每个金额都可以表示为一个参考硬币集，也可以表示为其中一个参考货币集加上一定数量的填充硬币。例如，如果数量为42，则可以表示为28+7+7或27+5+5+5。

注：参考金额必须是从24到30的连续整数，才能使填充硬币的值为7。这是一个棘手的部分

解决方案：

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循环来进行优化。

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

两种方法的时间比较：

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)

输出：

coin_count 0.022232770919799805
coin_count_optimized 0.0019953250885009766

代码可以如下所示：

def change(start, end):
    for i in range(start, end):
        ...
change(24,1000)

错误原因：此change函数接受的amount是一个整数输入。在这个change体的第一行中，我们有for i in amount。这个for循环期望amount是列表或元组、dict或迭代器。

这就是为什么你有'TypeError: 'int' object is not iterable'错误

我建议用户@rhurwitz提供的答案非常好，并建议您查看我的参考书-https://runestone.academy/runestone/books/published/pythonds/Recursion/WhatIsRecursion.html以便更好地理解递归。