The classic change-finding recursive algorithm

recursive_change.py

# gets combinations of coinage for your change 
# makes sure not to repeat combos by using skip_list
# generates partial solutions using partial_list
# when value is reached, partial_list is stuffed into final_list

def spare_a_dime_brotha(money, global_skip_list, global_partial_list, final_list):
	# make copies local to the scope
	partial_list = global_partial_list[:]
	skip_list = global_skip_list[:]
	
	if money >= 25 and not 'q' in skip_list:
		partial_list.append('q')
		spare_a_dime_brotha(money-25, skip_list, partial_list, final_list)
		partial_list.pop()
		skip_list.append('q')
		
	if money >= 10 and not 'd' in skip_list:
		partial_list.append('d')
		spare_a_dime_brotha(money-10, skip_list, partial_list, final_list)
		partial_list.pop()
		skip_list.append('d')

	if money >= 5 and not 'n' in skip_list:
		partial_list.append('n')
		spare_a_dime_brotha(money-5, skip_list, partial_list, final_list)
		partial_list.pop()
		skip_list.append('n')

	if money >= 1 and not 'p' in skip_list:
		partial_list.append('p')
		spare_a_dime_brotha(money-1, skip_list, partial_list, final_list)
		partial_list.pop()
		skip_list.append('p')

  	if money == 0:
		final_list.append(partial_list)


# user input asked for, then calculated
if __name__ == '__main__':
	pl = []
	fl = []
	sl = []
	user_value = input('Enter # of pennies: ')
	spare_a_dime_brotha(user_value, sl, pl, fl)
	print 'number of combinations:', len(fl)
	for l in fl:
		print l