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!!

nigonzalezm · Accepted Answer · 2014-11-26 01:58:23Z

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);

edited Nov 26, 2014 at 1:58

answered Nov 26, 2014 at 0:41

nigonzalezm

1902 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Junikin Over a year ago

Thank you for your answer however, as I may not get infinite 0's anymore, I do get infinite 1's. It's the part where I add the coin's to the ArrayList answerCoins that I am worried about, that's the part that makes it go infinite, I am hoping someone could help me fix those lines

Junikin Over a year ago

See my edit, I changed it to your solution, however it produces a Stack Overflow error when ran

nigonzalezm Over a year ago

you still have other errors, for example: in answerCoins.remove(coin), it must be answerCoins.remove(answerCoins.size() - 1), since you need to remove the last coins added.

nigonzalezm Over a year ago

Oh yes, but maybe that was my error, in my first post (before the edit) I advised to use for (Integer coin : coinsType), but actually that is not necessary, for (int coint = 0; i < coinsType.size(); ++coin) is correct in order to use coinsType.get(coin).

nigonzalezm Over a year ago

when change == 0 the function enters the if (change == 0) block, but also the else in your next if, since change == 0 the function will again run infinitely. Just change to if (change == 0) { ... } else if (change < 0) { ... } else { ... }

|

Collectives™ on Stack Overflow

Recursion Stack Overflow/Infinite-loop issue

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related