Clever Geek Handbook

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


source to share


3 answers


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

.

+8


source


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.

+2


source


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 .

+1


source






More articles:


All Articles