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)