count_change.py

def ways(amount, coin_types):
  
  """
    Python implementation for the counting_change problem
    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2
    
    Doesn't work for large numbers because we don't have tail call optimization in python
    
    Time complexity analysis: Found an explanation at 
    http://wqzhang.wordpress.com/2009/06/09/sicp-exercise-1-14/
  """
	if amount == 0:
		return 1

	if amount < 0 or len(coin_types) == 0:
		return 0

	coin_copy = list(coin_types)
	coin_copy.remove(coin_types[0])	

	without_first = ways(amount, coin_copy)
	with_first = ways(amount - coin_types[0], coin_types)

	return without_first + with_first