Why is the value of 'count' not kept across different recursions?

Question

This is Java code to count inversions in an array.

private void findInversions(int begin, int end, Integer count) {
    System.out.println("begin: " + begin + ", end: " + end + ", and count is " + count);
    if (end - begin < 1)
        return;
    int middle = (begin + end) / 2;
    findInversions(begin, middle, count);
    System.out.println("begin: " + begin + ", end: " + end + ", here count is " + count);
    findInversions(middle + 1, end, count);
    mergeAndCount(begin, middle, end, count);
    System.out.println("begin: " + begin + ", end: " + end + ", count now is: " + count);
}



private void mergeAndCount(int begin, int middle, int end, Integer count) {

    int[] result = new int[end - begin + 1];
    int aptr = begin;
    int bptr = middle + 1;
    for (int i = 0; i < result.length; i++) {
        if (aptr <= middle && bptr <= end) {
            if (numbers[aptr] < numbers[bptr]) {
                result[i] = numbers[aptr];
                aptr++;
            }
            else { // numbers[aptr] > numbers[bptr]
                // (a[aptr], b[bptr]) is an inversion here
                count++;
                System.out.println("Found: (" + numbers[aptr] + "," + numbers[bptr] + ") " + count);
                result[i] = numbers[bptr];
                bptr++;
            }
        }
        else if (aptr > middle) {
            result[i] = numbers[bptr];
            bptr++;
        }
        else if (bptr > end) {
            result[i] = numbers[aptr];
            aptr++;
        }

    }

    for (int i = 0; i < result.length; i++) {
        numbers[begin + i] = result[i];
    }

}

The inversions are printed just fine, but the count is never correct, because it loses its value after a recursive call returns. I've debugged couple of times and all I saw was that count became 0 again when a recursion ended, but I couldn't find why. Can anyone explain?

Why would you expect it to be preserved? Java uses pass-by-value for everything, including references such as to an `Integer` object. Note that `count++` will create a new `Integer` object; all the Java wrapper types are immutable. You could use an `AtomicInteger` as a mutable wrapper type if you wanted... — Jon Skeet, May 11 '16 at 13:08
because [`java is pass-by-value`](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) — SomeJavaGuy, May 11 '16 at 13:09
@EmanuelOster Yes it is. But even if it would not be, it wouldn't work, because of description in my answer. — Vampire, May 11 '16 at 13:12

score 2 · Accepted Answer · answered May 11 '16 at 13:10

2

Integer is an immutable class. When doing count++, the value is auto-unboxed to an int, this int is incremented and the result assigned to count. But you do not modify the instance you stuffed into the method. You could e. g. use an AtomicInteger instance and there use the incrementAndGet() or getAndIncrement() method.

answered May 11 '16 at 13:10

Vampire

35,631
4
76
102

Thanks, but why wouldn't it work either even if Integer was mutable? I mean then the value could be changed fine right? – Goh-shans May 11 '16 at 13:34
Could, but wouldn't. As you can read in my answer there is unboxing and then boxing with the new value assigned, so a new Object and not the same object modified. If `Integer` would be mutable **and** it had a method `increment()` **and** you would use it instead of `++` (No operator overloading in Java), **then** it would work, as it will if you use `AtomicInteger`, because all these are true for that. It adds some synchronisation overhead, so if performance is important, you might instead creat an own holder class with an int and an incrementing method to be used. – Vampire May 11 '16 at 13:43

score 1 · Answer 2 · answered May 11 '16 at 13:25

Your mergeAndCount() method should return the count it obtains. Methods calling those methods should use the return value. And I've kept it an Integer but there's no need; you can use the primitive int.

private Integer findInversions(int begin, int end, Integer count) {
    // ... do all your stuff here but change recursive calls:
    count += findInversions(begin, end, count);
    count += mergeAndCount(begin, middle, end, count0;
    // and return what you find
    return count;
}

private Integer mergeAndCount(int begin, int middle, int end, Integer count) {
    // ... do all your stuff here
    return count;
}

Your other alternative, since numbers is apparently a field on your counting class, is to keep count as a field in the class. That would have the same effect as what you seek.

Thanks for your time. I wanted to keep passing `count` as a parameter for an exercise in recursion (and thought!). I thought there was a bug in my code this whole time, so I insisted on keeping it this way and finding out why. And you can tell I'm not 'reputable' enough to upvote your answer. — Goh-shans, May 13 '16 at 13:42

Why is the value of 'count' not kept across different recursions?

2 Answers2