Home > DeveloperSection > Forums > Change parameter handled during recursion in Java
Ankita Pandey
Ankita Pandey

Total Post:183

Points:1285
Posted on    November-04-2014 10:32 PM

 Java Handler 
Ratings:


 1 Reply(s)
 538  View(s)
Rate this:
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?



Lillian Martin

Total Post:27

Points:189
Posted on    November-04-2014 11:45 PM

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

}


Don't want to miss updates? Please click the below button!

Follow MindStick