递归实现方法

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

制作递归的一般方法是想到两件事:

• 我什么时候可以轻松地提出答案？ - 这个问题的答案让你可以编写基本案例代码.在你的情况,你可以平凡产生答案时,两个列表中至少有一个是空的(结果是false)或两个非空列表的初始元素是相同的(结果是true)
• 当答案非常重要时,如何减少问题？ - 这个问题的答案让您决定如何进行递归调用.例如,在您进行递归调用^*之前,您可以删除其中一个列表的初始元素,或者ListIterator<Integer>代替List<Integer>非破坏性解决方案.

^*当然,在这种情况下,您需要注意在调用后添加数字,或者在启动递归链之前复制两个列表.