嘿，作为Python新手能尝试欧拉计划第31题还构思两种解法，已经超棒啦！先帮你把没写完的递归解法补全，再一步步解析思路～

给定一组硬币（如美元硬币集合{1,5,10,25}），找出凑成指定金额的所有组合方式。

补全后的递归解法代码 #

def count(s, m, n):
    # 如果剩余金额为负，说明当前组合无效
    if n < 0:
        return 0
    # 没有硬币可用但金额还没凑够，组合无效
    if m <= 0 and n >= 1:
        return 0
    # 金额刚好凑完，这是一种有效组合
    if n == 0:
        return 1
    # 递归分两种情况：不使用第m个硬币，或者使用第m个硬币
    return count(s, m - 1, n) + count(s, m, n - s[m-1])

代码思路解析 #

咱们来拆解每一行的逻辑，帮你彻底搞懂递归的核心：

• if n < 0: return 0：当减去某个硬币后剩余金额变成负数，说明这个硬币选多了，这种组合不算数，返回0
• if m <= 0 and n >= 1: return 0：硬币都用完了，但目标金额还没凑齐，自然没有有效组合，返回0
• if n == 0: return 1：刚好凑到目标金额，这是一种成功的组合，返回1来计数
• 最后一行的递归是关键：
  • count(s, m - 1, n)：不使用当前的第m个硬币，所以硬币数量减1，金额保持不变，计算这种情况下的组合数
  • count(s, m, n - s[m-1])：使用当前的第m个硬币，所以硬币数量不变（可以重复用同一种硬币），金额减去这个硬币的面值，计算剩余金额的组合数
  • 把两种情况的结果相加，就是总的组合数量啦

小提示 #

递归解法的思路特别直观，很适合新手理解，但它有个小问题：会有大量重复计算（比如不同的递归路径会计算同一个(m, n)的情况），如果目标金额很大或者硬币种类多，速度会变慢。你提到还有第二种解法，大概率是动态规划，刚好可以用dp数组来避免重复计算，优化效率哦～

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