Recursion Stack Overflow/Infinite-loop issue

Question

I was hoping someone could help me solve my problem of this Stack Overflow/Infinite-loop error and hopefully point me in the right direction. My program is designed to show all solutions of giving back change (change as in money) back to the user for a specified amount. The algorithm goes something 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 have so far

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 in values from a file, here is my test file I use

// Coins available in the USA, given in cents.  Very simple case.
1 5
9

After reading the file in, my ArrayList coinTypes will contain [1, 5] and my static int change will equal 9. So, the recursive algoritm below main, findChange will calculate all the different ways to make $0.09 with only pennies and a nickle, therefore all pennies should be the last solution output. But, I made an error in the for loop and I can't seem to fix it, here is my output

OUTPUT UPDATE

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 it does literally possible solution, but only the first two are the ones that matter, any ideas to fix?

WANT

Change: 9
[1 1 1 1 5]
[1 1 1 1 1 1 1 1 1]

Thank you for your time and efforts and thank you for any and all answers, if you need additional info please let me know. Keep in mind I am new to java and recursion so please bear with me. Thank you!!

Answer 1

In your function findChange, int coin is an index. You are using the index in the line:

answerCoins.add(coin);

instead of the values of the coinTypes list, so your first try is with a coin of 0 cents, hence the infinity loop, try changing to:

answerCoins.add(coinsType.get(coin));

You also need to change any other use of coin, for example in line:

findChange(change - coin, coinsType, answerCoins);

to

findChange(change - coinsType.get(coin), coinsType, answerCoins);