How can I check that all values are equal in an array using recursion?
I am trying to solve this algorithm recursively; I want to check that all values in an array are the same (or equal to each other). If all values are equal, return true, if they are not correct, return false. My code fails any tests.
public boolean allEqual(int[] a, int start, int end){
if (start > end) return false;
if (a.length==0) return false;
if (start==end && a[start] == a[end]) return true;
if (a[start] != a[end]){
return false;
}
return allEqual(a, start++, end);
}
change
return allEqual(a, start++, end);
to
return allEqual(a, start+1, end);
start++
passes the original value start
to the recursive call (which is what the post increment statement returns), so your recursion will never end and you will probably get StackOverflowError
.
It might be easiest to just take the first value of the array and go through until one value is the same.
public void allEqual(int[] arr) {
if(arr.length==0) return false;
for(int i=0; i<arr.length; i++)
if(arr[0]!=arr[i]) return false;
return true;
}
Edit: Implemented this answer to do this with recursion, and my answer doesn't.
You can solve this by using the classic division and conquest method. Split the array in halves until there are two elements, and then check if they are equal. Then conquer them and compare the values. Something like that:
class Ideone {
static boolean checkEquals(int a[], int start, int length) {
if (length==2)
return a[start]==a[start+1] && a[start]==a[0];
else
return checkEquals(a,start+0,length/2) &&
checkEquals(a,start+length/2,length/2);
}
public static void main (String[] args) {
int a[]={1,1,1,1,1,1,1,1};
System.out.println(checkEquals(a,0,8));
}
}
Done here .