爲什麼這個遞歸回溯函數比用於計算python中最小數量硬幣的非遞歸函數慢？

Question

我有這個代碼來計算硬幣的最小數量來做出改變。一個是由函數change調用的非遞歸版本和稱爲get_min_coin_configuration的遞歸回溯函數。在後一個函數中，我緩存了以前計算結果。我認爲這應該加快這個過程。但事實上，它比不緩存結果的非遞歸緩慢得多。任何線索爲什麼這是慢的？ 這裏是整個代碼

cat minimumcoinrecurse.py 
import timeit 
def change(amount): 
    money =() 
    for coin in [25,10,5,1]: 
     num = amount/coin 
     money += (coin,) * num 
     amount -= coin * num 

    return money 

#print change(63) 
def get_min_coin_configuration(sum=None, coins=None, cache=None): 
    if cache == None: # this is quite crucial if its in the definition its presistent ... 
     cache = {} 
    if sum in cache: 
     return cache[sum] 
    elif sum in coins: # if sum in coins, nothing to do but return. 
     cache[sum] = [sum] 
     #print cache 
     return cache[sum] 
    elif min(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do. 
     cache[sum] = [] 
     return cache[sum] 
    else: # check for each coin, keep track of the minimun configuration, then return it. 
     min_length = 0 
     min_configuration = [] 
     for coin in coins: 
      results = get_min_coin_configuration(sum - coin, coins, cache) 
      if results != []: 
       if min_length == 0 or (1 + len(results)) < len(min_configuration): 
        #print "min config", min_configuration 
        min_configuration = [coin] + results 
        #print "min config", min_configuration 
        min_length = len(min_configuration) 
        cache[sum] = min_configuration 
     #print "second print", cache 
     return cache[sum] 
def main(): 
    print "recursive method" 
    print "time taken", 
    t=timeit.Timer('get_min_coin_configuration(63,[25,10,5,1])',"from __main__ import get_min_coin_configuration") 
    print min(t.repeat(3,100)) 
    print get_min_coin_configuration(63,[25,10,5,1]) 
    print '*'*45 
    print "non-recursive" 
    print "time taken", 
    t1=timeit.Timer('change(63)',"from __main__ import change") 
    print min(t1.repeat(3,100)) 
    print change(63) 
if __name__ == "__main__": 
    main() 

輸出：

recursive method 
time taken 0.038094997406 
[25, 25, 10, 1, 1, 1] 
********************************************* 
non-recursive 
time taken 0.000286102294922 
(25, 25, 10, 1, 1, 1) 

Answer 1

緩存是不是在你的評估中使用。此外，每次運行都會重建。通過explicetely指定它與

cache = {} 
def main(): 
    print "recursive method" 
    print "time taken", 

使用緩存比較：

t=timeit.Timer('get_min_coin_configuration(63, [25,10,5,1], cache)', 
        'from __main__ import get_min_coin_configuration, cache') 
    print min(t.repeat(3,100)) 
    print get_min_coin_configuration(63,[25,10,5,1]) 
    print '*'*45 
    print "non-recursive" 
    print "time taken", 
    t1=timeit.Timer('change(63)',"from __main__ import change") 
    print min(t1.repeat(3,100)) 
    print change(63) 

recursive method 
time taken 8.26920739926e-05 
[25, 25, 10, 1, 1, 1] 
********************************************* 
non-recursive 
time taken 0.000361219093488 
(25, 25, 10, 1, 1, 1)