CODEWITHSUNDEEP
javaconcurrency
ocaptchamycaptcha
ocaptchamycaptcha

Reputation: 185

ConcurrentModificationException using Recursion in Java

So I am getting the following runtime error:

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at Solution.getAnswers(Solution.java:53)
at Solution.getAnswers(Solution.java:44)
at Solution.getAnswers(Solution.java:44)
at Solution.getEquations(Solution.java:28)
at Solution.main(Solution.java:22)

Now I have read up on the exception and am confused as to why this is happening, since to my knowledge I do not execute any code asynchronously. I know an array list is not thread safe, but I am not sure why adding values to a list would be a problem. Also I did not think I would have concurrency issues using recursion.

If any one could shed some light on the issue, and why it is happening it would be much appreciated! My code is below, and I believe the error originates in the recursive method found at the end of my code. 

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        long result = getEquations(a,b);
        System.out.println(result);
    }

    private static long getEquations(int a, int b) {
        ArrayList<Integer> answers = new ArrayList<Integer>();
        getAnswers(a,b,answers);
        return answers.stream().mapToInt(x->x).distinct().count();
    }

    private static void getAnswers(int a, int b, ArrayList<Integer> answers){
        if(a==0 && b==0) return;
        if(a==1 && b == 0) {
            answers.add(1);
            return;
        }
        if(a==0 && b == 1) {
            answers.add(2);
            return;
        }
        if(a>0){
            a-=1;
            getAnswers(a,b,answers);
            for(Integer value : answers){
                answers.add(1+value);
                answers.add(1*value);
            }
            return;
        }
        if(b>0){
            b-=1;
            getAnswers(a,b,answers);
            for(Integer value : answers){
                answers.add(2+value);
                answers.add(2*value);
            }
            return;
        }
    }
}

Upvotes: 2

Views: 1490

Answers (4)

Jhonny007
Jhonny007

Reputation: 1798

While @shmosel has already given the formal answer I'll try to illustrate the problem a bit more:

Think about a List<Integer> list with the values {1, 2, 3, 4, 5, 6} the size of the list is obviously 6.

Now instead of using the iterator magic that java gives us we use the good old for loop:

for(int i = 0; i < list.size(); i++) {
    int someValue = doSomeMath();
    list.add(someValue);
}

Here is how the iterations would look like:
i -> 0, list.size() -> 6
i -> 1, list.size() -> 7
i -> 2, list.size() -> 8
i -> 3, list.size() -> 9

Since we are adding a value to the list in every iteration, we will be stuck in an infinite loop, because we will never get to i == list.size() since the list is growing with the same rate as we iterate.

To prevent this behavior the iterator (in a for(Integer value : list) loop) throws the exception, because it could never finish if we would add values while iterating.

Upvotes: 1

Jarred Allen
Jarred Allen

Reputation: 362

The answer by @shmosel is generally good, however, it will not work if the order of items is important to your code. If this matters, you can replace this:

        for(Integer value : answers){
            answers.add(1+value);
            answers.add(1*value);
        }

with this:

        ArrayList<Integer> toAdd=new ArrayList<Integer>();
        for(Integer value : answers){
            toAdd.add(1+value);
            toAdd.add(1*value);
        }
        answers.addAll(toAdd);

This new code will still produce answers in the same order.

If you are only calling getAnswers from getEquations, then this won't matter because your getEquations is independent of the order of the items in the arraylist, but it may be a consideration depending on if there is or may one day be other code.

Upvotes: 3

erickson
erickson

Reputation: 269847

In your loop, you modify the collection while iterating. That's not allowed.

for(Integer value : answers) { /* Iterator is created implicitly here */
  answers.add(1+value);        /* Underlying collection is modified here */
  ...

The only permissible modification is to call remove() on an Iterator instance.

Upvotes: 1

shmosel
shmosel

Reputation: 50756

Read the documentation:

Note that this exception does not always indicate that an object has been concurrently modified by a different thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception.

Your code is throwing this exception because you're modifying the list while iterating. Consider using a ListIterator which will allow you to safely insert (at the current position) while iterating.

Upvotes: 9

Related Questions