求助：使用Tree Recursion实现美元硬币找零问题（禁用循环）

先修正你代码里的基础错误，再给出正确的递归实现：

你的代码存在的问题 #

• next_smaller_coin函数中，条件判断用了赋值运算符=，应该改为相等判断==，这是语法错误。
• count_coins函数中未定义coins变量，且递归逻辑错误：wo_coin = count_coins(change)会无限递归调用自身，直接导致栈溢出。
• 缺少“当前允许使用的最大硬币面值”这个关键递归参数，无法区分“使用当前面值硬币”和“改用更小面值硬币”的分支逻辑。

正确的递归实现思路 #

递归的核心是分两种情况拆解问题：

1. 使用当前最大面值的硬币：剩余找零金额减去该面值，继续用这个面值递归（因为同面值硬币可以重复使用）。
2. 不使用当前最大面值的硬币：转而使用下一个更小的面值，剩余找零金额保持不变。
   终止条件：

• 剩余金额为0：找到1种有效组合，返回1。
• 剩余金额小于0：组合无效，返回0。
• 没有更小的硬币可用（即当前面值为1之后再找更小的）且剩余金额不为0：组合无效，返回0。

修正后的代码 #

def next_smaller_coin(coin):
    """返回下一个更小面值的硬币"""
    if coin == 25:
        return 10
    elif coin == 10:
        return 5
    elif coin == 5:
        return 1
    else:  # 当硬币是1时，没有更小的了
        return None

def count_coins(change, current_coin=25):
    if change == 0:
        return 1
    if change < 0:
        return 0
    # 如果当前没有可用硬币了，且change不为0，返回0
    if current_coin is None:
        return 0
    
    # 情况1：使用当前面值的硬币
    with_coin = count_coins(change - current_coin, current_coin)
    # 情况2：不使用当前面值，改用更小的硬币
    wo_coin = count_coins(change, next_smaller_coin(current_coin))
    
    return with_coin + wo_coin

代码说明 #

• next_smaller_coin函数新增了对1的处理，返回None表示没有更小的硬币。
• count_coins新增了current_coin可选参数，默认从最大面值25开始递归。
• 每次递归同时计算“用当前硬币”和“不用当前硬币”的组合数，相加得到总组合数。
• 所有终止条件都覆盖了边界情况，避免无限递归。

测试示例：

print(count_coins(10))  # 输出4：10；5+5；5+1*5；1*10
print(count_coins(25))  # 输出13

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