ConcurrentModificationException using Recursion in Java

Question

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

shmosel · Accepted Answer · 2016-09-05 02:03:06Z

9

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.

answered Sep 5, 2016 at 2:03

shmosel

51k7 gold badges81 silver badges148 bronze badges

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

Comments

Jarred Allen · Accepted Answer · 2016-09-05 02:38:43Z

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.

erickson · Accepted Answer · 2016-09-05 02:18:55Z

1

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.

answered Sep 5, 2016 at 2:18

erickson

271k59 gold badges406 silver badges502 bronze badges

Comments

Jhonny007 · Accepted Answer · 2016-09-05 14:16:17Z

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.

Collectives™ on Stack Overflow

ConcurrentModificationException using Recursion in Java

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related