Iterating through arraylists with recursion
I wrote a method that basically checks if all elements from two ArrayLists are equal, and if so, return true. I believe this method works, however, I would also like to write this same method purely with recursion without using any loops, which means I would have to replace the loop for the loop. 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;
}
Java provides the method that I suggest you use ( equals(Object)
). Also, your method signature should look bigger (note the <T>
pre-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 are the same size, and all matching pairs of elements in the two lists are equal.
To do it recursively, you can 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;
}
source to share
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);
source to share
I assume you want to do this recursively for educational purposes (there really is no point in doing this for any other reason: the best is to use an existing library routine, and the best is to use a loop for
you already did).
The general approach to using recursion is that you solve your problem by finding one or more smaller versions of the same problem in your problem. Thus, to compare arrays for equality, if the arrays are of length N, you can write a recursive method
-
comparison of the first elements, and then (less problem) recursive comparison of the last two elements of the two arrays, which will be arrays of length N-1; or
-
comparing the last elements and then (less problem) recursively comparing the subarrays that are the first N - 1 elements of each array; or
-
if you really need some good practice, split each array in half (two smaller problems) and then compare the left halves for equality and the right halves for equality.
To get smaller arrays, you probably don't want to create new arrays by copying the elements - too slow. Instead, you can write a method that only takes the first and last subarray index as parameters, and then your recursive method will assume that the portion of the larger array between those boundaries is the smaller subarray it deals 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, which is what @alfasin's solution does. It assumes that the subarray it works with has 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 are of length 0. (Or, when subarrays are of length 1, you can compare individual elements and not call the method recursively. Your choice.) For the third approach, when you divide the subarrays in half, you need to stop with a subarray of length 1 - otherwise if you try to split it in half, you have one array of length 0 and one of length 1, and the latter won't be any smaller problem !!
Anyway, this is a rather long answer, and of course, much more than you need to compare two arrays for equality. But I'm trying to give you a basic idea of how you might approach other problems where you really need recursion.
source to share