java - Java 递归期间如何处理参数更改？

Question

这是一个递归方法:

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

我要 sum1和 sum2要在相同的 triangle 上计算目的。但是，会发生以下情况:在 sum1 之后计算，一行 triangle (然后是递归中的另一个和另一个......)。现在，当 sum2计算它有一个 triangle那是空的!

这让我对 Java 如何处理递归感到困惑。为什么是对象triangle被修改？我假设它应该是每个递归级别的“本地”数据。

我们如何重写代码以获得所需的行为？

例如，让我们说 triangle对象有两行(由两个整数列表给出)。 sum1应该从第一行获取一些东西，然后递归调用 triangle 上的方法只剩下一行了。同样， sum2也应该从第一行获取一些东西，然后递归调用 triangle 上的方法只剩下一行了。但是，我看到的是以下内容。后 sum1计算， triangle是空的。因此， sum2分配了错误的值!

Answer 1

只有一个 List<List<Integer>> triangle实例。对该实例的引用传递给每个递归调用，但对该实例所做的任何更改都会反射(reflect)在递归的所有级别中。

看起来您想在每次递归调用中处理下一行三角形，并且您通过删除第一行来实现它(以便下一次递归调用具有不同的第一行)。如果是这种情况，则不必删除第一行。只需将索引传递给该行，以便每个递归调用都知道它应该处理哪一行。

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