在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！

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

2. 如何重写代码以获得所需的行为？

---

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

Answer 1

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

它看起来像你想要在每次递归调用中处理下一行三角形，并且通过删除第一行（以便下一个递归调用具有不同的第一行）来实现它。如果是这样的话，你不必删除第一行。只需将一个索引传递给该行，以便每次递归调用都知道应该使用哪一行。

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

你改变这里triangle参数内部状态：

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

既然你打电话minimumTotal一遍又一遍，在每一个递归调用triangle损失一行。这与Java（或任何其他编程语言）如何处理递归无关，而与您在递归调用中做什么有关。

如果您只想要/需要检索位置0上的元素，请使用triangle.get(0)。如果您需要删除，但只有在完成必要的操作后才能删除，请仅在执行所需操作后再致电triangle.remove。如果您没有删除triangle的内部列表，请使用triangle.get(index)并通过index作为参数。

Answer 3

在Java中，除了原始类型（int，boolean，char等。）一切是引用类型。这意味着你实际上在变量中所持有的只是对实际对象的引用。如果将它传递给方法，则引用会被复制，但它仍指向内存中的同一个对象。这意味着递归方法的每次调用都指向相同的triangle对象，并且由于第一次递归调用会从List中删除所有项目，因此第二次调用将始终只给出空的List。

直接的方法是在每次递归调用之前创建List的两个副本，并将这些副本的引用传递给它们。然而，这将是一种非常耗时且效率低下的方式。

我会建议在递归调用中添加第三个参数，说明从哪里开始计算。该方法不会以任何方式更改原始的triangle。

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

你的初始呼叫应该是这样的：

minimumTotal(triangle, index, 0); 

这种方法甚至会比你原来的速度更快，因为remove(0)是O（N）操作。