How is a parameter change handled during recursion in Java?

Question

Here is a recursive method:

private static int minimumTotal(List<List<Integer>> triangle, int index) { 
    if (triangle.isEmpty()) { 
        return 0; 
    } 

    List<Integer> row = triangle.remove(0); 

    int sum1 = row.get(index) + minimumTotal(triangle, index);
    int sum2 = row.get(index) + minimumTotal(triangle, index + 1);
    return Math.min(sum1, sum2); 
}

I want sum1 and sum2 to be calculated on the same triangle object. However, what happens is the following: after sum1 is calculated, one row of triangle (and then another within the recursion and another ...). Now, when sum2 is calculated it has a triangle that is empty!

1. This confuses me regarding how Java handles recursion. Why is the object triangle getting modified? I was under the assumption that it should be a "local" data at every recursion level.

2. How can we rewrite the code to get the desired behavior?

---

As an example, lets say the triangle object has two rows (given by two list of integers). sum1 is supposed to get something from the first row and then recursively call the method on the triangle that has only one row remaining. Similarly, sum2 is also supposed to get something from the first row and then recursively call the method on the triangle that has only one row remaining. However, what I see is the following. After sum1 is computed, triangle is empty. Thus, sum2 is assigned a wrong value!

Answer 1

There is only one List<List<Integer>> triangle instance. The reference to that instance is passed to each recursive call, but any change done to this instance is reflected in all levels of the recursion.

It looks like you want to process the next row of triangle in each recursive call, and you achieve it by removing the first row (so that the next recursive call has a different first row). If that's the case, you don't have to remove the first row. Just pass an index to the row, so that each recursive call knows which row it should work on.

private static int minimumTotal(List<List<Integer>> triangle, int rowIndex, int colIndex) { 
    if (rowIndex >= triangle.size()) { 
        return 0; 
    } 

    List<Integer> row = triangle.get(rowIndex); 

    int sum1 = row.get(colIndex) + minimumTotal(triangle, rowIndex + 1, colIndex);
    int sum2 = row.get(colIndex) + minimumTotal(triangle, rowIndex + 1, colIndex + 1);
    return Math.min(sum1, sum2); 
}

Answer 2

In Java, everything except the primitive types (int, boolean, char, etc..) is a reference type. It means that what you actually hold in the variable is just a reference to the actual object. If you pass it to a method, the reference gets copied, but it still points to the same object in memory. That means that every call of your recursive method points to the same triangle object and since the first recursive call removes all the items from the List, the second call will always be given just the empty List.

The straightforward way would be to create a two duplicates of the List before each recursive call and passing references to those duplicates. This would, however, be a very time consuming and inefficient way.

I would suggest adding a third parameter to the recursive call saying where to start with the calculation. The method wouldn't change the original triangle in any way.

private static int minimumTotal(List<List<Integer>> triangle, int index, int from) { 
    if (from >= triangle.size()) { 
        return 0; 
    } 

    List<Integer> row = triangle.get(from); 

    int sum1 = row.get(index) + minimumTotal(triangle, index, from + 1);
    int sum2 = row.get(index) + minimumTotal(triangle, index + 1, from + 1);
    return Math.min(sum1, sum2); 
}

Your initial call would look like this:

minimumTotal(triangle, index, 0);

This method will even be faster than your original one, because remove(0) is an O(N) operation.