注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为7分钟。
上一节提到，贪心策略会有失效的情况，如何在不依赖某种硬币体系的情况下找到找零硬币最少个数的最优解？
这就要求我们找一种“能行”的找到最优解的方法。所谓“能行”，是指不依赖于类似于美元那种固定的四种面值的硬币体系。
递归就是这么一种“能行”的方法。
递归解决找零问题的最优解
套用递归的三个条件：
兑换￠63的例子。
1）确定基本结束条件：需要兑换的找零，其面值正好等于某个货币单位，比如找零是￠25，就给1个￠25的硬币。
2）其次是减小问题的规模，我们要对每种硬币尝试1次，例如美元硬币体系：
- 找零减去￠1后，求兑换硬币最少数量（递归调用自身，第3个条件）；
- 找零减去￠5后，求兑换硬币最少数量；
- 找零减去￠10后，求兑换硬币最少数量；
- 找零减去￠25后，求兑换硬币最少数量；
最后选择上面结果中最小的一个。
numCoins = min(1+numCoins(originalamout-1), 1+numCoins(originalamount-5), 1+numCoins(original-10), 1+nuCoins(originalamount-25))。
具体代码实现如下：
# 递归解决找零问题v1。
import time
start = time.time()
def recMC(coinValueList, change):
minCoins = change
if change in coinValueList:
return 1 # 最小规模，直接返回。
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList, change - i) # 调用自身和减少规模。
if numCoins < minCoins:
minCoins = numCoins
return minCoins
print(recMC([1, 5, 10, 25], 63))
end = time.time()
print(f"运行本递归程序一共用了{end - start}秒。")
<<<
6
运行本递归程序一共用了37.6766254901886秒。
<<<
递归解决之道的问题
递归方法虽然“能行”，也就是能解决问题，但是其最大的问题在于：极其低效！！！
上述案例中，兑换￠63，需要进行67,716,925次递归调用。本计算机花了37秒时间才得到答案。
以26分兑换硬币为例，看看递归调用过程（377次递归的一小部分）。结果发现，重复计算太多，例如找零15分的出现了三次，而最终解决还要52次递归调用。而实际上一次就够了。所以递归算法的致命缺点就是重复的计算太多了。
递归解法的改进
对递归解法进行改进，关键之处就在于消除重复计算：
用一个表将计算过的中间结果保存起来，在计算之前查看表，看是否已经计算过。所谓中间结果，就是部分找零的最优解，在递归调用过程中已经得到的最优解被记录下来。在递归调研之前先查表是否已有部分找零的最优解，如果有，直接返回最优解而不是进行递归调用；如果没有，才进行递归调用。
# 递归解决找零问题v2。
import time
start = time.time()
def recMC(coinValueList, change, knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1 # 记录最优解。
return 1 # 最小规模，直接返回。
elif knownResults[change] > 0:
return knownResults[change] # 查表成功，直接用最优解。
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList, change - i, knownResults) # 调用自身和减少规模。
if numCoins < minCoins:
minCoins = numCoins
# 找到最优解，记录到表中。
knownResults[change] = minCoins
return minCoins
print(recMC([1, 5, 10, 25], 63, [0] * 64))
end = time.time()
print(f"运行本递归程序一共用了{end - start}秒。")
<<<
6
运行本递归程序一共用了0.0009992122650146484秒。
<<<
可以看到，优化过后的程序运行时间从约38秒降低至1毫秒。
改进之后的解法，极大地减少了递归调用次数。对63分兑换硬币问题，仅仅需要221次递归调用，是改进之前的三十万分之一，程序效率得到极大提升。
To be continued.
