方法的递归实现

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>进行非破坏性解决方案之前删除其中一个列表的初始元素。

^*当然在这种情况下，你需要照顾的任何电话后加入你的号码回，或者在开始递归链之前使两个名单的副本。