make_change.rb

#
# http://rubyquiz.com/quiz154.html
#

def make_change(amount, available_change, coins = [])
  raise "not enough available change" if(amount > 0 && available_change.empty?)
  return coins if amount == 0
  
  coin = available_change.shift
  n = amount / coin
  
  if n > 0
    make_change(amount - coin*n, available_change, coins + n.times.collect{coin})
  else
    make_change(amount, available_change, coins)
  end
end

p make_change(52, [100, 25, 1]).inspect   # [25, 25, 1 1]
p make_change(52, [25, 10, 5, 1]).inspect # [25, 25, 1 1]
p make_change(52, [10, 5, 1]).inspect     # [10, 10, 10, 10, 10, 1, 1]
p make_change(52, [10, 5]).inspect        # exception