The obvious answer is to memoize count-change. A similar approach is to use dynamic programming. In python: def count_change(change): return count(change, len(coin_value)) def count(change, num_coins): result=[[0 for j in range(num_coins)] for i in range(change + 1)] for i in range(change + 1): for j in range(num_coins): if i == 0: # exact change IS possible with given coin_value result[i][j] = 1 elif j == 0: # no coins left, still change to give result[i][j] = 0 elif coin_value[j] > i: # current coin is too large result[i][j] = result[i][j-1] else: # tally how many ways we can get here from previous results result[i][j] = result[i-coin_value[j]][j] + result[i][j-1] return result[change][num_coins-1] >>> count_change(100) 292 coin_value = [0, 1, 5, 10, 25, 50] >>> from count_change import count_change