iterating through arraylists with recursion

Question

I have written a method that basically checks to see if all the elements in two ArrayLists are equal and if so, return true. I believe this method works, however, I'd like to also write this same method solely using recursion without using any loops, meaning that I'd have to replace the for loop block. Any suggestions or hints?

public static boolean isEqual(ArrayList<O> arrlist1, ArrayList<O> arrlist2) {
        ArrayList<O> um=new ArrayList<O>();
        ArrayList<O> um2=new ArrayList<O>();
        um=arrlist1;
        um2=arrlist2;
        boolean comp=false;
        if (um.size()==um2.size()){
            for (int i=0; i<um.size(); i++){
                if (um.get(i)==(um2.get(i)))
                    comp=true;
                else
                    comp=false;
            }
        }
        return comp;    
    }

Answer 1

I'm assuming you want to do this recursively for learning purposes (there's really no point in doing it for any other reason; it's best to use an existing library routine, and next-best to use a for loop like you already did).

The general approach to using recursion is that you're going to solve your problem by finding one or more smaller versions of the same problem within your problem. So, to compare arrays for equality, if the arrays are of length N, you can write a recursive method by

• comparing the first elements, and then (smaller problem) recursively comparing the 2nd through last elements of the two arrays, which will be arrays of length N - 1; or

• comparing the last elements, and then (smaller problem) recursively comparing the subarrays that are the first N - 1 elements of each array; or

• if you really want good practice, divide each array in half (two smaller problems) and then compare the left halves for equality, and the right halves for equality.

To get the smaller arrays, you probably don't want to create new arrays by copying elements--too slow. Instead, you can write a method that takes just the first and last index of the subarray as parameters, and then your recursive method will assume that the portion of the larger array between those boundaries is the smaller subarray it's dealing with. (Or if the first index is the same every time, or the last index is the same every time, you only need to pass one parameter; that's what @alfasin's solution does. It assumes that the subarray it's working with has the bounds n and arrlist1.size()-1.)

You also need to figure out when to stop. For the first two approaches, you can stop when your subarrays have length 0. (Or when the subarrays have length 1, you can compare the single elements and not call the method recursively. Your choice.) For the third approach, when you divide subarrays in half, you have to stop with a subarray of length 1--otherwise, if you tried to divide it in half, you'd have one array of length 0 and one of length 1--and the last is not a smaller problem!!

Anyway, this is a pretty lengthy answer, and certainly a lot more than you need to compare two arrays for equality. But I'm trying to give you the basic idea of how you could approach other problems where you really do need recursion.

Answer 2

Recursive version:

public static boolean isEqual(ArrayList<O> arrlist1, ArrayList<O> arrlist2, int n) {
    if (arrlist1.size() == n && arrlist1.size() == arrlist2.size()) {
        return true;
    } else {
           if (arrlist1.get(n).equals(arrlist2.get(n))) {
               return isEqual(arrlist1, arrlist2, n + 1);
           }
           else {
               return false;
           }
    }
}

and it should be called like this:

 isEqual(arrlist1, arrlist2, 0);

Answer 3

Java provides a method to do that I suggest you use it (equals(Object)). Also, your method signature should look more like this (note the <T> before boolean).

public static <T> boolean isEqual(List<T> arrlist1, List<T> arrlist2) {
    if (arrlist1.size() == arrlist2.size()) {
        return arrlist1.equals(arrlist2);
    }
    return false;
}

From the Javadoc,

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal.

To do it recursively, you could use List#subList(int,int) with something like

public static <T> boolean isEqual(List<T> arrlist1, List<T> arrlist2) {
    if (arrlist1.size() == arrlist2.size()) {
        if (arrlist1.get(0).equals(arrlist2.get(0))) {
            if (arrlist1.size() == 1) {
                return true;
            }
            return isEqual(arrlist1.subList(1, arrlist1.size()),
                    arrlist2.subList(1, arrlist2.size()));
        }
    }
    return false;
}