Recursion stack overflow / infinite loop problem
I was hoping someone could help me solve my problem of this error / infinite loop and hopefully point me in the right direction. My program is designed to display all decisions to return changes (change in cash) back to the user for a certain amount. The algorithm looks like this:
Subtract a coin amount from the total change value. If you get back 0,
then is a solution
If negative, discard that coin.
If you try a nickle and it doesn't work, un-choose it, try a penny
This is what I still have
import java.io.*;
import java.util.*;
import java.lang.*;
public class homework5 {
public static int change;
public static void main(String[] args)
throws FileNotFoundException { //begin main
ArrayList<Integer> coinTypes = new ArrayList<Integer>();//array to store coin types
ArrayList<Integer> answerCoins = new ArrayList<Integer>();//answer to be outputted
Integer i;
File f = new File (args[0]);
Scanner input = new Scanner(f); //initialize scanner
input.nextLine();
while(input.hasNextInt()) {
i = input.nextInt();
coinTypes.add(i); //add all ints to file
}
change = coinTypes.get(coinTypes.size()-1);
coinTypes.remove(coinTypes.size()-1);
System.out.println("Change: " + change);
findChange(change, coinTypes, answerCoins);
}
private static void findChange(int change, List<Integer> coinTypes, List<Integer> answerCoins) {
//contains means of finding the
//change solutions
if(change == 0) {
//base case
System.out.println(answerCoins);
}
else if(change < 0) {
//if negative it can't be a solution
} else {
for(int coin = 0; coin < coinTypes.size(); coin++) {
answerCoins.add(coinTypes.get(coin)); //choose
findChange(change-coinTypes.get(coin), coinTypes, answerCoins);//explore
answerCoins.remove(answerCoins.size()-1); //un-choose
}
}
}
}
As I mentioned, the program reads values from a file, here is my test file which I am using
// Coins available in the USA, given in cents. Very simple case.
1 5
9
After reading the file, my ArrayList
coinTypes
will contain [1, 5]
and mine static int
change
will be 9
. So the recursive algorithm below the main one findChange
will calculate all the different ways to make $ 0.09 with just a penny and a nickel, so all pennies should be the last output of the solution. But I made a mistake in the for loop and I cannot fix it, here is my output
UPDATE OUTPUT
Change: 9
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 5]
[1, 1, 1, 5, 1]
[1, 1, 5, 1, 1]
[1, 5, 1, 1, 1]
[5, 1, 1, 1, 1]
As you can see this makes literally a possible solution, but only the first two are important, any ideas for a fix?
WANTS
Change: 9
[1 1 1 1 5]
[1 1 1 1 1 1 1 1 1]
Thanks for your time and effort and thank you for any responses, if you need more information please let me know. Keep in mind that I'm new to java and recursion, so please bear with me. Thank!!
source to share
In your findChange function, int coin
is the index. You are using the index on the string:
answerCoins.add(coin);
instead of list values coinTypes, so your first try is with 0 cent coin, hence infinity loop, try changing to:
answerCoins.add(coinsType.get(coin));
You also need to change any other usage of the coin, for example in the line:
findChange(change - coin, coinsType, answerCoins);
to
findChange(change - coinsType.get(coin), coinsType, answerCoins);
source to share