I am writing a java recursive method that accepts an array and returns that true when each element is twice the value of the previous element. I can't figure out the base case yet, because it is returning true for each case. Any help will be appreciated.

    public class testRecursion {

    public static void main(String[] args) {
        System.out.print(isDouble(new int[]{2 ,3, 4, 5, 6, 7}, 5));

    }
    public static boolean isDouble(int[] array,int i) {
        //base case
        if(i == array.length - 1)
            return true;
        //recursive case
        if(array[i 1] != array[i] * 2)
            return false;
        else
            return isDouble(array, i);
    }   
}

CodePudding user response：

Here is one method.

int[][] test = {{2,4}, {1},{2,3}, {6,12,24},{6,12,24,47},
        {2,4,8,16,32,64,128}, {}, null};
for (int[] t : test) {
     System.out.printf("%5s - %s%n", isDouble(t), Arrays.toString(t));
}

prints

 true - [2, 4]
false - [1]
false - [2, 3]
 true - [6, 12, 24]
false - [6, 12, 24, 47]
 true - [2, 4, 8, 16, 32, 64, 128]
false - []
false - null

You only need to pass the array.

• for each recursive call, copy the array sans the last element.
• make the call ANDing with current result (a single false comparison will return false).

public static boolean isDouble(int[] array) {
    if (array == null || array.length <= 1) {
        return false;
    }
    int len = array.length;
    if (array[len-1] != array[len-2]*2) {
        return false;
    }
    if (array.length >=3 ) {
        return isDouble(Arrays.copyOf(array, len-1));       
    }
    return true;
}

Here is one way to do it with passing an index of 0. Using a call of isDouble(array,0) prints the same as above. It is essentially the same as above except no array is being copied (so it is somewhat more efficient).

public static boolean isDouble(int[] array, int n) {
    if (array == null || array.length <= 1) {
        return false;
    }
    int len = array.length;
    if (array[len-1] != array[len-2]*2) {
        return false;
    }
    if (n < len-2) {
        return isDouble(array, n 1);
    }
    return true;
}

But the most efficient way would be a simple loop. As soon as a false condition is exposed the result can be returned immediately with no "unwinding" of the recursive calls.

CodePudding user response：

This is correct??

public class testRecursion {

    public static void main(String[] args) {
        System.out.print(isDouble(new int[]{2 ,3, 4, 5, 6, 7}, 5));

    }
    public boolean isDouble(int[] array,int i) {
            //base case
            if(i == 1) {
                if(array[i] == array[i-1] * 2)
                    return true;
                else
                    return false;
            }else {
                 if(isDouble(array, i-1)) {
                    if(array[i] == array[i-1] * 2)
                        return true;
                    else
                        return isDouble(array, i-1);
                 }else {
                     return false;
                 }
            }
        }
}