ConcurrentHashMap throws recursive update exception

Question

Here is my Java code:

static Map<BigInteger, Integer> cache = new ConcurrentHashMap<>();

static Integer minFinder(BigInteger num) {
        if (num.equals(BigInteger.ONE)) {
            return 0;
        }
        if (num.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            //focus on stuff thats happening inside this block, since with given inputs it won't reach last return
            return 1 + cache.computeIfAbsent(num.divide(BigInteger.valueOf(2)),
                    n -> minFinder(n));
        }
        return 1 + Math.min(cache.computeIfAbsent(num.subtract(BigInteger.ONE), n -> minFinder(n)),
                cache.computeIfAbsent(num.add(BigInteger.ONE), n -> minFinder(n)));
    }

I tried to memoize a function that returns a minimum number of actions such as division by 2, subtract by one or add one. The problem I'm facing is when I call it with smaller inputs such as:

minFinder(new BigInteger("32"))

it works, but with bigger values like:

minFinder(new BigInteger("64"))

It throws a Recursive Update exception. Is there any way to increase recursion size to prevent this exception or any other way to solve this?

According to the docs, a recursive update exception implies you're making one entry in the map have a value that depends on itself, which is impossible to define. Consider logging the values of `num` you're working on to try to trace where that happens. — Louis Wasserman, Feb 11 '22 at 23:32

John Bollinger · Accepted Answer · 2022-02-11T23:43:09.480

From the API docs of Map.computeIfAbsent():

The mapping function should not modify this map during computation.

The API docs of ConcurrentHashMap.computeIfAbsent() make that stronger:

The mapping function must not modify this map during computation.

(Emphasis added)

You are violating that by using your minFinder() method as the mapping function. That it seems nevertheless to work for certain inputs is irrelevant. You need to find a different way to achieve what you're after.

Is there any way to increase recursion size to prevent this exception or any other way to solve this?

You could avoid computeIfAbsent() and instead do the same thing the old-school way:

BigInteger halfNum = num.divide(BigInteger.valueOf(2));
BigInteger cachedValue = cache.get(halfNum);

if (cachedValue == null) {
    cachedValue = minFinder(halfNum);
    cache.put(halfNum, cachedValue);
}
return 1 + cachedValue;

But that's not going to be sufficient if the computation loops. You could perhaps detect that by putting a sentinel value into the map before you recurse, so that you can recognize loops.

ConcurrentHashMap throws recursive update exception

1 Answers1

Linked