/**
 * A class that uses recursion to make change
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
    public class ChangeMaker4 
   {
      private int counter;
      
       public ChangeMaker4 ()
      {
         counter = 0;
      }	
   	
       public int getCounter()
      {
         return counter;
      }
   	
    /**
     * 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;
         int temp1, temp2;     
      	 
         counter++;
         System.out.println (" on entry to change, when counter is " + counter + 
                             " amount is " + amount);
      
         min = amount;
         System.out.println (" min has changed to " + min);						                
      // 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++) 
         {
         
            System.out.println (" calling change with (coins, j) ");
            temp1 = change(coins,j);
            System.out.println (" calling change with (coins, amount-j" );
            temp2 = change(coins, amount - j);
            number = temp1 + temp2;
            //number = change(coins, j) + change(coins, amount-j);
         	
            System.out.println (" number has changed to " + number);
            if (number < min) min = number;
         }
      
         return min;
      }
   
   }