如何用递归实现最小硬币找零问题？

看起来你现在的代码只完成了贪心思路的第一步，完全没用到递归逻辑，所以才会只返回第一个面额的硬币。我来帮你调整成递归实现，同时解决贪心算法在部分场景下无法得到最优解的问题（比如你第二个测试用例里的[6,1,4]凑8，贪心会拿[6,1,1]，但最优是[4,4]）。

首先先明确你的需求：给定总金额和硬币面额，返回最少硬币数量的组合，用递归实现。

先分析你现有代码的问题 #

• 没有递归调用：collect_coins函数只处理了第一个面额，没有对剩余金额和剩下的面额进行递归处理
• 修改了原面额列表：denominations.pop(0)会直接修改传入的列表，导致后续逻辑出错
• 贪心思路局限性：只取当前最大面额的最大数量，这种方法只在特定面额体系（比如美元硬币）下有效，无法应对所有场景

递归实现的核心思路 #

递归的关键是把大问题拆解成小问题：

1. 对于当前面额，尝试使用0到最多能使用的数量（比如总金额18，面额10最多用1个）
2. 对每种使用数量，递归处理剩余金额和剩下的面额
3. 在所有可能的组合中，筛选出硬币数量最少的那个

修正后的递归代码 #

def r_change_money(total, denominations):
    # 先将面额降序排序，优先尝试大面额（优化递归效率，不影响结果正确性）
    sorted_denoms = sorted(denominations, reverse=True)
    
    def recursive_helper(remaining_amount, current_denoms):
        # 终止条件1：剩余金额为0，说明凑成了，返回空列表表示不需要更多硬币
        if remaining_amount == 0:
            return []
        # 终止条件2：剩余金额为负，或者没有可用面额了，返回None表示该组合无效
        if remaining_amount < 0 or not current_denoms:
            return None
        
        best_comb = None
        current_coin = current_denoms[0]
        # 计算当前硬币最多能使用的数量
        max_possible = remaining_amount // current_coin
        
        # 从最多数量往下尝试，能更快找到最优解（因为大硬币用得多的话数量更少）
        for count in range(max_possible, -1, -1):
            # 递归处理剩余金额和剩下的面额
            sub_comb = recursive_helper(remaining_amount - count * current_coin, current_denoms[1:])
            if sub_comb is not None:
                # 组合当前使用的硬币和子问题的结果
                current_comb = [current_coin] * count + sub_comb
                # 更新最优组合：要么是第一个有效组合，要么是更短的组合
                if best_comb is None or len(current_comb) < len(best_comb):
                    best_comb = current_comb
        
        return best_comb
    
    return recursive_helper(total, sorted_denoms)

# 测试用例1：预期输出 [10, 5, 1, 1, 1]
print(r_change_money(18, [1, 10, 5]))

# 测试用例2：预期输出 [4, 4]（而非贪心的[6,1,1]）
print(r_change_money(8, [6, 1, 4]))

代码解释 #

• 外层函数先对面额降序排序，这样递归时优先尝试大面额，能更快找到短组合，提升效率
• recursive_helper是核心递归函数，负责处理剩余金额和当前可用面额
• 遍历当前硬币的所有可能使用数量，递归获取子问题的解，然后组合成完整的硬币列表
• 每次都保留硬币数量最少的组合，最终返回最优解

运行这段代码，你就能得到预期的结果啦～

备注：内容来源于stack exchange，提问作者haltersweb