CODEWITHSUNDEEP
javarecursion
user3242081
user3242081

Reputation: 1

Split an amount into dimes, nickels and pennies recursively

I wrote the following code:

public class CoinChange
{
    static int n = 0;
    static int count = 0; 
    public static void main (int value) {
        n = value;
        recursiveLoop(0, 0, 0, 0);
    }        
    private static int recursiveLoop(int i, int j, int k, int l)
    {
        if ((i + (5 * j) + (10 * k) + (25 * l)) == n)
            count ++;
        l++;
        if (l > n / 25)
        {
            l = 0;
            k++;
        }
        if (k > n / 10)
        {
            k = 0;
            j++;
        }

        if (j > n / 5)
        {
            j = 0;
            i++;
        }  
        if (i>n)
        { 
            System.out.println("Number ways " + n + 
            " can be changed is " + count + ".");
            System.exit(0);
        } 
        recursiveLoop(i, j, k, l);
        return count;
    }
}

This code is working fine til 50 cents but when I give an input greater than 50, I get a stack overflow error. Please help me identify the problem with this program.

Upvotes: 0

Views: 138

Answers (2)

Bobby Treat
Bobby Treat

Reputation: 1

Clear[change]
units = {10000, 5000, 2000, 1000, 500, 100, 25, 10, 5, 1};
names = {"$100", "$50", "$20", "$10", "$5", "$1", "quarter", "dime", 
   "nickel", "penny"};
toUnit = Dispatch@Thread[units -> names];
fromUnit = Dispatch@Thread[names -> units];
change[0] := Sequence[]
change[n_Integer?Positive] := 
 change[n] = Module[{large = Max@Cases[units, x_ /; x <= n], t},
   Flatten@{ConstantArray[large /. toUnit, t = Floor[n/large]], 
     change[n - t large]}
   ]
Total /@ (Array[change, lim = 100000] /. fromUnit) == Range[lim]

Tally@Flatten@Array[change, 1000]

Upvotes: 0

Jesse Jashinsky
Jesse Jashinsky

Reputation: 10683

The only return you have is right after the recursive call. That means your current program will never break out of the recursion. You need to check for a "done" condition and return if "done" is true. Or, have recursiveLoop(i, j, k, l); be under the if statement.

Upvotes: 1

Related Questions