在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）操作。