/**
 * A class that uses recursion to make change
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
    public class ChangeMaker 
   {
      private int counter;
      
       public ChangeMaker ()
      {
         counter = 0;
      }	
    /**
     * Determine the minimum number of coins needed to make change
     *
     * @param coins  The array of coin values
     * @param amount The amount of change
     *
     * @returns      The number of coins
     */
       public int change(int[] coins, int amount)
      {
         int i, j, min, number;
      
         min = amount;
         counter++;
      
      // If we can make change with one coin then we are done
      //
         for (i=0; i < coins.length; i++) {
         
            if (coins[i] == amount) 
               return 1; // The base case
         }
      
      // Refine the solution
      //
         for (j=1; j <= (amount/2); j++) {
         
            number = change(coins, j) + change(coins, amount-j);
            if (number < min) min = number;
         }
      
         return min;
      }
   
   }