Recursion Coin Change

Question

Need help figuring out how to print the individual coins such as quarters = 3, pennies = 1, instead of just giving me 4 coins for 76 cents. I tried setting 4 counters, but that just repeatedly printed out the coin names and answers were wrong.

import java.util.Scanner;
public class Money
{
    public static void main(String args[])
    {
        int[] coins = { 1, 5, 10, 25};
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter Change (In Cents): ");
        int sum = scan.nextInt();
        int counter1 = 0;
        int counter2 = 0;
        int counter3 = 0;
        int counter4 = 0;
        String quarter = "";
        Money minCoin = new Money();
        System.out.println(minCoin.findMinCoins(coins, sum, counter1, counter2, counter3, counter4));
        System.out.println(counter4);
    }

    private int findMinCoins(int[] coins, int sum, int counter1, int counter2, int counter3, int counter4)
    {
        if (sum <= 0 || coins.length == 0)
        {
            return 0;
        }

        for (int i = coins.length - 1; i >= 0; i--)
        {
            if(coins[i] == 1 && coins[i] != 5)
            {
                counter1++;
            }

            if(coins[i] == 5)
            {
                counter2++;
            }

            if(coins[i] == 10)
            {
                counter3++;
            }

            if(coins[i] == 25)
            {
                counter4++;
            }

            if (coins[i] <= sum)
            {
                System.out.println("Pennies: " + counter1);
                System.out.println("Nickels: " + counter2);
                System.out.println("Dimes: " + counter3);
                System.out.println("Quarters: " + counter4);
                return 1 + findMinCoins(coins, sum - coins[i], counter1, counter2, counter3, counter4);

            }
        }
        return 0;
    }

}

In your return statement, you have 1 + findMinCoins... but that doesn't really provide information as to what kind of coin the 1 represents. Instead, try adding 1 to the variables within the return statement, for example: findMinCoins(coins, sum - coins[i], counter1 + 1,...) to show that you needed another penny — Morgan Hill, Nov 29 '16 at 04:13

score 0 · Answer 1 · answered Nov 29 '16 at 04:38

Try this:

import java.util.Scanner;
public class Money
{
public static void main(String[] args) {

        int[] coins = {1, 5, 10, 25};
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter Change (In Cents): ");
        int sum = scan.nextInt();
        int counter1 = 0;
        int counter2 = 0;
        int counter3 = 0;
        int counter4 = 0;
        String quarter = "";
        Money minCoin = new Money();
        System.out.println(minCoin.findMinCoins(coins, sum, counter1, counter2, counter3, counter4));
        System.out.println(counter4);

    }

    private int findMinCoins(int[] coins, int sum, int counter1, int counter2, int counter3, int counter4) {
        if (sum <= 0 || coins.length == 0) {
            return 0;
        }

        for (int i = coins.length - 1; i >= 0; i--) {

            if (coins[i] == 25 && sum >= coins[i]) {
                counter4++;

            }

            else if (coins[i] == 10 && sum >= coins[i]) {
                counter3++;
            }

            else if (coins[i] == 5 && sum >= coins[i]) {
                counter2++;
            }

            else if (coins[i] == 1 && sum >= coins[i]) {
                counter1++;
            }

            if (coins[i] <= sum) {
                System.out.println("Pennies: " + counter1);
                System.out.println("Nickels: " + counter2);
                System.out.println("Dimes: " + counter3);
                System.out.println("Quarters: " + counter4);
                return 1 + findMinCoins(coins, sum - coins[i], counter1, counter2, counter3, counter4);

            }
        }
        return 0;
    }
}

Please consider adding some additional information to your answer explaining your changes. :) — Gulllie, Nov 29 '16 at 04:48

score 0 · Answer 2 · edited May 23 '17 at 10:32

I suspect you have misunderstood how arguments passed to Java methods work. You are passing in the 'counter' values and then iterating them inside the method and expecting their values in the calling method to have changed. That's not how Java works. See here for more details.

If you're not expecting to get the values back from the method (because you're printing them inside) then there's no point making them arguments. Best to make it a local variable inside the scope of the method.

You might find it a bit easier if you order from largest to smallest and return an array from your change calculator. Then you won't need individual variables for your counters.

Something like the following:

int[] coins = {25, 10, 5, 1};
String[] names = {"Quarters", "Dimes", "Nickles", "Pennies"};
int[] change = getChange(coins, total);
for (int i = 0; i < change.length; i++) {
    System.out.println(names[i] + ":" + change[i]);
}

private int[] getChange(int[] coins, int total) {
    int[] result = new int[coins.length];
    for (int i = 0; i < coins.length; i++) {
        result[i] = total / coins[i];
        total -= result[i] * coins[i];
    }
    return result;
}

Note that this takes advantage of Java's integer division rounding down. So if you start with 76 cents it will return 3 quarters (76/25 -> 3). Note also that the second statement in the loop could be total %= coins[i] which would have the same effect but might be more understandable. Either way the code is saying 'remove from the total the value of the current denomination`.

Recursion Coin Change

2 Answers2