Recursive implementation of a method

Question

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.

Are the two integer lists ordered? If not the first version of the function won't work. — Marcy
– Marcy, Commented Jun 11, 2016 at 10:27

Sergey Kalinichenko · Accepted Answer · 2016-06-11 10:39:52Z

5

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.

edited Jun 11, 2016 at 10:39

answered Jun 11, 2016 at 10:32

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Daniel Netzer Over a year ago

why destroying the lists though, as I do like your answer cause it helps thinking about recursion in general, he might aswell iterate over both of the lists and check for HaveNext() or some sort of other way to check for end of the list to keep them intact.

katto ch Over a year ago

Thanks @dasblinkenlight for explaining how to tackle recursion in general.

Marcy · Accepted Answer · 2016-06-11 10:32:55Z

4

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

answered Jun 11, 2016 at 10:32

Marcy

3,0261 gold badge27 silver badges37 bronze badges

1 Comment

katto ch Over a year ago

Thanks for the demonstration @Leon, it does give me an idea on how to construct the method.

Collectives™ on Stack Overflow

Recursive implementation of a method

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related