递归实现硬币凑指定金额报错单次递归次数过多 如何解决？

• 递归无收敛逻辑：你代码中的递归调用possiblechange(total, coins)没有修改任何入参，每次调用的参数和父级完全一致，永远无法命中前面的返回条件，会无限递归直到触发Python的递归深度限制，最终抛出递归次数过多的错误。
• 递归逻辑错误：将布尔类型的递归返回值和硬币面值相乘的操作没有任何实际意义，完全不符合「选定一枚硬币后，计算剩余金额和剩余硬币数是否符合要求」的核心逻辑。
• 存在浮点数精度隐患：直接用十进制小数表示金额做相等判断，很容易因为浮点数精度丢失出现误判，比如0.1 + 0.2 != 0.3的经典问题。

正确的递归逻辑应该是每次选定一枚硬币后，将剩余金额减去对应面值、剩余硬币数减1，再判断新的状态是否合法，直到触发边界条件。同时建议将金额统一转成美分的整数计算，避免精度问题。
修复后的代码如下：

def possiblechange(total_dollar, coin_count):
    # 转换为美分整数，规避浮点数精度问题
    total_cents = int(round(total_dollar * 100))
    # 四种硬币对应的美分数值
    denominations = [1, 5, 10, 25]

    def dfs(remaining_cents, remaining_coins):
        # 边界1：刚好用完所有硬币凑够金额
        if remaining_cents == 0 and remaining_coins == 0:
            return True
        # 边界2：硬币耗尽或金额超额，直接剪枝返回
        if remaining_coins == 0 or remaining_cents < 0:
            return False
        # 遍历所有面值，递归判断剩余状态
        for d in denominations:
            if dfs(remaining_cents - d, remaining_coins - 1):
                return True
        return False

    is_possible = dfs(total_cents, coin_count)
    if is_possible:
        print(f"可使用{coin_count}枚硬币凑出{total_dollar}美元")
    else:
        print(f"无法使用{coin_count}枚硬币凑出{total_dollar}美元")
    return is_possible

# 测试示例
possiblechange(1.0, 4)
possiblechange(1.0, 5)
possiblechange(1.0, 6)
possiblechange(1.25, 5)

如果需要处理金额和硬币数更大的场景，可以给递归函数加上记忆化缓存，避免重复计算相同状态：
只需要引入functools.lru_cache给内部dfs函数加上装饰器即可：

from functools import lru_cache

def possiblechange(total_dollar, coin_count):
    total_cents = int(round(total_dollar * 100))
    denominations = [1, 5, 10, 25]

    @lru_cache(maxsize=None)
    def dfs(remaining_cents, remaining_coins):
        if remaining_cents == 0 and remaining_coins == 0:
            return True
        if remaining_coins == 0 or remaining_cents < 0:
            return False
        for d in denominations:
            if dfs(remaining_cents - d, remaining_coins - 1):
                return True
        return False

    is_possible = dfs(total_cents, coin_count)
    if is_possible:
        print(f"可使用{coin_count}枚硬币凑出{total_dollar}美元")
    else:
        print(f"无法使用{coin_count}枚硬币凑出{total_dollar}美元")
    return is_possible

内容的提问来源于stack exchange，提问作者Zy Taga