Why this recursive backtracking function slower than the non-recursive one for calculating minimum number of coins for change in python?

Question

I have this code for calculating minimum no of coins to make a change. one is non-recursive version which is called by function change and the recursive-backtrack function called get_min_coin_configuration. In the latter function, I cache the results from the previously calculated ones. I thought that should speed up the process. but in fact, it's much slower than the non-recursive one which does not cache the results. any clue why this is slower? here is the entire code

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()

output:

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

Cache is not used in your evaluation. Moreover, it is rebuilt with each run. Compare with

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

use cache by explicetely specifying it:

    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)