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 a triangle (and then another within the recursion and another ...). Now, when sum2 has 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?
Lillian Martin
04-Nov-2014There 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.