Scala递归countChange找零计数函数的求值顺序疑问

这个内层递归函数的拆分逻辑是把所有找零方案做无重叠、无遗漏的枚举：每一步只针对当前列表里的第一枚硬币，把所有方案分成两类：

• 第一类：只要方案里至少用了这枚硬币，就把钱数扣掉这枚硬币的面值，依然保留所有硬币的选择权限（毕竟用了一次之后还可以继续用同面值的）
• 第二类：只要方案里完全没用到这枚硬币，就把这枚硬币从可选列表里删掉，钱数不变

两类方案的数量加起来，就是当前参数下的总找零数。递归的终止判断非常明确：

• 钱数刚好凑到0：返回1，代表当前路径成功凑出了一组合法找零
• 钱数超了（小于0），或者没有硬币可选了：返回0，代表当前路径走不通

这组参数对应的合法找零一共3种，分别是：

• 4张1元
• 2张1元 + 1张2元
• 2张2元

完整的递归计算链路：

• 入口countChangeRec(4, List(1,2)) 拆成两个大分支相加
  • 分支1：至少用1张1元，进入countChangeRec(3, List(1,2))
    • 该节点继续拆：countChangeRec(2, List(1,2)) + countChangeRec(3, List(2))
      • 第一个子节点：用1张1元凑3元，剩2元
        • 拆为：countChangeRec(1, List(1,2)) + countChangeRec(2, List(2))
          • 孙节点1：用1张1元凑2元，剩1元
            • 拆为：countChangeRec(0, List(1,2)) + countChangeRec(1, List(2))
              • 前者凑完刚好0元，返回1（对应4张1元的方案）；后者剩1元要用2元硬币凑，完全走不通，返回0
              • 本节点结果：1+0=1
          • 孙节点2：不用1元，剩2元全用2元凑
            • 拆为：countChangeRec(0, List(2)) + countChangeRec(2, List())
              • 前者用1张2元凑完2元，返回1（对应2张1元+1张2元的方案）；后者硬币列表空了，返回0
              • 本节点结果：1+0=1
        • 这部分总结果：1+1=2
      • 第二个子节点：不用1元，剩3元全用2元凑
        • 拆为：countChangeRec(1, List(2)) + countChangeRec(3, List())
          • 前者用1张2元后剩1元，凑不出来，返回0；后者硬币空了，返回0
          • 本节点结果：0+0=0
    • 分支1总结果：2 + 0 =2
  • 分支2：完全不用1元，进入countChangeRec(4, List(2))
    • 拆为：countChangeRec(2, List(2)) + countChangeRec(4, List())
      • 前者用1张2元后剩2元
        • 拆为：countChangeRec(0, List(2)) + countChangeRec(2, List())
          • 前者再用1张2元凑完0元，返回1（对应2张2元的方案）；后者硬币空了，返回0
          • 本节点结果：1+0=1
      • 后者硬币空了，返回0
    • 分支2总结果：1 +0 =1
• 最终结果：分支1的2 + 分支2的1 =3

你在推导时直接跳过了递归的嵌套层级，把不同节点的计算结果平铺合并，漏掉了最顶层预留的“完全不使用1元硬币凑4元”的分支，也就是全用2元的那组合法方案，因此得到了2的错误结果。

另外外层的边界判断逻辑：

• 当入参钱数为0、或者硬币列表为空时直接返回0，是为了把递归内部的边界逻辑和外层的调用语义隔离开——比如外部调用countChange(0, List(1,2))时，本身不需要统计0元的找零方式，因此外层直接返回0，不会进入递归的计算流程。

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