/**
 * A class that uses recursion to make change
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
public class ChangeMaker
{

    /**
     * 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;
			System.out.println (" entered change with amount = " + amount);
			
	    
				// If we can make change with one coin 
				// then we are done
 			for (i=0; i < coins.length; i++) 
			{
	    	  	if (coins[i] == amount) // The base case
					return 1; 
			}
	
				// 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;

    } // end Change

} // end ChangeMaker