如何遞歸查找鏈表中的最大值？

我需要在給定列表頭以遞歸方式作爲參數的鏈表中找到最大值。我不知道如何啓動該方法的遞歸部分。這是我迄今爲止所有的。如何遞歸查找鏈表中的最大值？

int maxOfList(List M){ 
    List max = M; 
    if(M == null) 
     return max; 
    if(M.next > max){ 
     max = M.restOfTheInts; 
     return maxOfList(); 
    } 
}

來源

2016-03-23 cee

做什麼，你有一個長1名列表到目前爲止的工作？如果不是，甚至不要試圖考慮遞歸情況。（提示：不，它不會） –

在遞歸中，您經常需要一個入口方法和一個工作方法。入口方法是一種特殊情況，它允許工作方法在所有情況下工作，並且工作人員執行遞歸。

例如，你的工人可能是這樣的：

int maxOfList(int currentMax, List<int> listToCheck) { 
    // Nothing to compare? currentMax is it! 
    if (listToCheck == null || listToCheck.size() == 0) return currentMax; 

    // Compare and return. 
    List<int> restOfList = listToCheck.subList(1, listToCheck.size()); 
    return maxOfList(Math.max(currentMax, listToCheck.get(0)), restOfList); 
}

然後踢其關閉，您需要進入方法：

int maxOfList(List<int> listToCheck) { 
    return maxOfList(Integer.MIN_VALUE, listToCheck); 
}

來源

2016-03-23 03:05:18

這只是作爲一個優化需要，如果它將尾調用優化。沒有尾部呼叫優化，不需要輔助方法。 –

這就是其中一個原因。另一個原因是，遞歸方法的簽名幾乎總是帶有一個僅用於遞歸的參數。在這種情況下，'currentMax'是一個參數，而不是公共API不需要知道的。 –

我的觀點是，你根本不需要參數，因此不需要幫手。遞歸調用只是'return max（node.value，maxOfList（node.tail））' –

所以，遞歸有效工作，需要在函數內部看到整個上下文。

int maxOfList(List m) { 
    if(m.next == null) 
      return m; 
    int previousMax = maxOfList(m.next); 
    if(m > previousMax) 
      return m; 
    else 
      return previousMax; 
}

來源

2016-03-23 03:10:55 pranshuagarwal

你可能需要提供一個'List.next'的實現來完全解釋。 –

同意保羅。我的答案只是一個算法解決方案。在我看來，實現到Java語言應該留給cee讓他有效地理解遞歸。 – pranshuagarwal

int maxValue(List m){ 
    return maxValue(m, Integer.MIN_VALUE); 
} 

int maxValue(List m, int num){ 
    if(m.next == null){ 
    if(m.data > num) 
    return num = m.data; 
    } 
    return maxValue(m.next, num); 
}

來源

2016-03-23 03:20:21 Zeus

這應該是非常簡單的。爲了實現遞歸解決方案，請考慮所有這些步驟：