/**
 * A class that uses recursion to make change
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
public class ChangeMaker
{
   // #9
	int count;
	
    /**
     * 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;

      // #9
	   count++;  
	   System.out.println
		(" in change for " + count + " time: amount = " + amount); 	
	// If we can make change with one coin then we are done
	//
	for (i=0; i < coins.length; i++) 
	{
	  System.out.print
	  ("                     			i = " + i  );
	  System.out.println();                    
      if (coins[i] == amount)
		    return 1; // The base case
	}
	
	// Refine the solution
	//
	for (j=1; j <= (amount/2); j++) 
	{
	    System.out.println
		 ("                          										 j = " + j);  
		 number = change(coins, j) + change(coins, amount-j);
	    if (number < min) 
		     min = number;
	}
	
	return min;
  } // end method change

  public int getCount()
  {
    return count;
  }

}// end class ChangeMaker