CODEWITHSUNDEEP
javarecursion
katto ch
katto ch

Reputation: 109

Recursive implementation of a method

I'm new to Java and still trying to wrap my head around recursion.The function below returns true at the very first intersection between the two sorted lists list x and list y.

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;
}

Now I've been trying to implement it using recursion instead, and I know that there should be a base case which is an empty list in this case and then try to reduce the list by excluding one element at a time and feed it back to the same recursive function, but I can't work out how to check for intersection as I pass the rest of the list over and over.

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);
    }
}

Any help would be highly appreciated. Thank you.

Upvotes: 1

Views: 120

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

General approach to making something recursive is to think of two things:

  • When can I produce an answer trivially? - An answer to this question lets you code the base case. In your situation, you can produce the answer trivially when at least one of two lists is empty (the result would be false) or the initial elements of both non-empty lists are the same (the result would be true)
  • How do I reduce the problem when the answer is non-trivial? - An answer to this question lets you decide how to make your recursive call. In your case you could, for example, remove the initial element of one of the lists before making the recursive call*, or pass ListIterator<Integer> in place of List<Integer> for a non-destructive solution.

*Of course in this case you need to take care of either adding your numbers back after the call, or make a copy of two lists before starting the recursive chain.

Upvotes: 5

Leon
Leon

Reputation: 3036

As the lists are ordered, your recursion should remove the first element of the list with the smaller first value. Then you have to return true, if both lists start with the same number and false if any of the lists is empty. Otherwise you keep removing elements. This would look something like this (This code is untested):

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));
        }
    }
}

Upvotes: 4

Related Questions