硬币找零递归算法展开：为何加1及正确展开方法问询

先解答「为什么要加1」 #

这个1是当前选中的那枚硬币的计数，核心逻辑很好理解：
当你选了一枚面值为i的硬币，那这枚硬币本身就要算1枚。递归调用rec_coin(target-i, coins)是在计算「凑出剩下的target-i金额需要多少枚硬币」，把这两个数加起来，才是「选了这枚i硬币后，凑出原target金额的总硬币数」。

举个简单例子：目标金额是5，硬币数组是[1,5]

• 如果选了面值1的硬币，那剩下的4需要4枚1，总硬币数就是1 + 4 = 5
• 如果直接选面值5的硬币，触发base case（target在coins里），直接返回1，这就是最优解

正确的递归展开方式（以rec_coin(63,[1,5,10,25])为例） #

我们直接看最优路径的展开（递归会遍历所有可能路径，最后取最小值）：

1. 初始调用：rec_coin(63, [1,5,10,25])
   • 遍历到硬币25，计算1 + rec_coin(63-25=38, coins)
2. 进入rec_coin(38, coins)
   • 遍历到硬币25，计算1 + rec_coin(38-25=13, coins)
3. 进入rec_coin(13, coins)
   • 遍历到硬币10，计算1 + rec_coin(13-10=3, coins)
4. 进入rec_coin(3, coins)
   • 遍历到硬币1，计算1 + rec_coin(3-1=2, coins)
5. 进入rec_coin(2, coins)
   • 遍历到硬币1，计算1 + rec_coin(2-1=1, coins)
6. 进入rec_coin(1, coins)
   • 触发base case：1在coins数组里，返回1

把这些加起来：1+1+1+1+1+1=6，刚好是题目给出的正确结果。

你之前理解的1 + 63-1 + 62-1 + ...是错误的，因为递归的每一步不是累加减法，而是每选一枚硬币就计1次，然后递归求解剩余金额的子问题，最后把所有选中的硬币数加起来。

另外补充一句：原递归代码存在大量重复计算（比如rec_coin(3)会被多次调用），实际工程中会用记忆化搜索或者动态规划来优化，但这是另一个话题啦。

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