注：本文如涉及到代碼，均經(jīng)過Python 3.7實際運行檢驗，保證其嚴(yán)謹(jǐn)性。

本文閱讀時間約為7分鐘。

上一節(jié)提到，貪心策略會有失效的情況，如何在不依賴某種硬幣體系的情況下找到找零硬幣最少個數(shù)的最優(yōu)解？

這就要求我們找一種“能行”的找到最優(yōu)解的方法。所謂“能行”，是指不依賴于類似于美元那種固定的四種面值的硬幣體系。

遞歸就是這么一種“能行”的方法。

遞歸解決找零問題的最優(yōu)解

套用遞歸的三個條件：

兌換￠63的例子。

1）確定基本結(jié)束條件：需要兌換的找零，其面值正好等于某個貨幣單位，比如找零是￠25，就給1個￠25的硬幣。

2）其次是減小問題的規(guī)模，我們要對每種硬幣嘗試1次，例如美元硬幣體系：

• 找零減去￠1后，求兌換硬幣最少數(shù)量（遞歸調(diào)用自身，第3個條件）；
• 找零減去￠5后，求兌換硬幣最少數(shù)量；
• 找零減去￠10后，求兌換硬幣最少數(shù)量；
• 找零減去￠25后，求兌換硬幣最少數(shù)量；

最后選擇上面結(jié)果中最小的一個。

numCoins = min(1+numCoins(originalamout-1), 1+numCoins(originalamount-5), 1+numCoins(original-10), 1+nuCoins(originalamount-25))。
具體代碼實現(xiàn)如下：

# 遞歸解決找零問題v1。
import time
start =  time.time()
def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        return 1  # 最小規(guī)模，直接返回。
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change - i)  # 調(diào)用自身和減少規(guī)模。
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

print(recMC([1, 5, 10, 25], 63))
end = time.time()
print(f"運行本遞歸程序一共用了{(lán)end - start}秒。")

<<<
6
運行本遞歸程序一共用了37.6766254901886秒。
<<<

遞歸解決之道的問題

遞歸方法雖然“能行”，也就是能解決問題，但是其最大的問題在于：極其低效?。?！

上述案例中，兌換￠63，需要進行67,716,925次遞歸調(diào)用。本計算機花了37秒時間才得到答案。

以26分兌換硬幣為例，看看遞歸調(diào)用過程（377次遞歸的一小部分）。結(jié)果發(fā)現(xiàn)，重復(fù)計算太多，例如找零15分的出現(xiàn)了三次，而最終解決還要52次遞歸調(diào)用。而實際上一次就夠了。所以遞歸算法的致命缺點就是重復(fù)的計算太多了。

遞歸解法的改進

對遞歸解法進行改進，關(guān)鍵之處就在于消除重復(fù)計算：

用一個表將計算過的中間結(jié)果保存起來，在計算之前查看表，看是否已經(jīng)計算過。所謂中間結(jié)果，就是部分找零的最優(yōu)解，在遞歸調(diào)用過程中已經(jīng)得到的最優(yōu)解被記錄下來。在遞歸調(diào)研之前先查表是否已有部分找零的最優(yōu)解，如果有，直接返回最優(yōu)解而不是進行遞歸調(diào)用；如果沒有，才進行遞歸調(diào)用。

# 遞歸解決找零問題v2。
import time
start =  time.time()
def recMC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1  # 記錄最優(yōu)解。
        return 1  # 最小規(guī)模，直接返回。
    elif knownResults[change] > 0:
        return knownResults[change]  # 查表成功，直接用最優(yōu)解。
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change - i, knownResults)  # 調(diào)用自身和減少規(guī)模。
            if numCoins < minCoins:
                minCoins = numCoins
                # 找到最優(yōu)解，記錄到表中。
                knownResults[change] = minCoins
    return minCoins

print(recMC([1, 5, 10, 25], 63, [0] * 64))
end = time.time()
print(f"運行本遞歸程序一共用了{(lán)end - start}秒。")

<<<
6
運行本遞歸程序一共用了0.0009992122650146484秒。
<<<

可以看到，優(yōu)化過后的程序運行時間從約38秒降低至1毫秒。
改進之后的解法，極大地減少了遞歸調(diào)用次數(shù)。對63分兌換硬幣問題，僅僅需要221次遞歸調(diào)用，是改進之前的三十萬分之一，程序效率得到極大提升。

To be continued.