方法的遞歸實現

Question

我是Java新手，仍然試圖圍繞遞歸進行打包。下面的函數在兩個排序列表列表x和列表y之間的第一個交集處返回true。

public static boolean checkIntersection(List<Integer> x, List<Integer> y) { 
    int i = 0; 
    int j = 0; 
    while (i < x.size() && j < y.size()) { 
     if (x.get(i).equals(y.get(j))) { 
      return true; 
     } else if (x.get(i) < y.get(j)) { 
      i++; 
     } else { 
      j++; 
     } 
    } 
    return false; 
} 

現在，我一直在嘗試使用遞歸，而不是實現它，我知道應該有一個基本情況是在這種情況下，一個空的列表，然後嘗試通過排除在一個元素，以減少列表一段時間，並將其反饋回相同的遞歸函數，但我無法弄清楚如何檢查交集，因爲我一遍又一遍地傳遞列表的其餘部分。

public static boolean recursiveChecking(List<Integer> x,List<Integer> y) { 
    if(x.size() == 0){ 
     return false; 
    } 
    else { 
     return recursiveChecking(x.subList(1, x.size()-1), y); 
    } 
} 

任何幫助將不勝感激。謝謝。

Answer 1

由於列表是按順序排列的，因此遞歸應該使用較小的第一個值來移除列表的第一個元素。然後你必須返回true，如果兩個列表以相同的數字開始，如果任何列表爲空，則返回false。否則，你不斷移除元素。這看起來像這樣（此代碼未經測試）：

public static boolean recursiveChecking(List<Integer> x,List<Integer> y) { 
    if(x.size() == 0 || y.size() == 0){ 
     return false; 
    } else if (x.get(0).equals(y.get(0))) { 
     return true; 
    } else { 
     if (x.get(0) < y.get(0)) { 
      return recursiveChecking(x.subList(1, x.size()-1), y); 
     } else { 
      return recursiveChecking(x, y.subList(1, y.size()-1)); 
     } 
    } 
} 

Answer 2

通用的方法，使一些遞歸是考慮兩件事情：

• 我什麼時候可以平凡產生一個答案？ - 對這個問題的回答可以讓你編碼基本情況。在這種情況下，當兩個列表中的至少一個爲空（結果爲false）或兩個非空列表的初始元素相同（結果爲true）時，您可以輕鬆地生成答案
• 如果答案不平凡，我該如何減少問題？ - 這個問題的答案可以讓你決定如何進行遞歸調用。例如，您可以在遞歸調用^*或刪除List<Integer>以代替List<Integer>進行非破壞性解決方案之前刪除其中一個列表的初始元素。

^*當然在這種情況下，你需要照顧的任何電話後加入你的號碼回，或者在開始遞歸鏈之前使兩個名單的副本。