I have to create a method (int[]v, int a, int b) in java using recursion that takes an array of integers and returns an array in which between every two elements of the array there must be the value a or the value b, alternately.

For example, if an array v = {1,5,6,8}, when i call the method like this (v,0,1) the method should return {1,0,5,1,6,0,8}.

Any kind of pseudo code would help, I'm really struggling to implement this. Thanks!

CodePudding user response：

Let me know if it does what you need

yourMethod(int[] v, int a, int b){
    int[] newArray = new int[v.length*2-1];
    int counter = 0;
    boolean alter = true;

    for(int i=0; i<newArray.length; i  ){
        if(i%2==0){
            newArray[i] = v[counter];
            counter  ;
        }else{
            if(alter){
                newArray[i] = a;
                alter = !alter;
            }else{
                newArray[i] = b;
                alter = !alter;
            }
        }
    }
}

CodePudding user response：

First, we need a way to concatenate arrays, since they can't be resized in Java:

int[] concat(int[] p, int[] q) {
    int[] result = new int[p.length   q.length];
    System.arraycopy(p, 0, result, 0, p.length);
    System.arraycopy(q, 0, result, p.length, q.length);
    return result;
}

Then, we need a recursive definition:

• Base case: If the array is not of at least length 2, just return the array.
• Recursive Case: Return the concatenation of an array of the first element and a with the method applied to the tail of the array (from the second element on) with a and b swapped.

Swapping the values gives us the desired alternation between the values.

int[] inject(int[] v, int a, int b) {
    if (v.length < 2) return v;
    return concat(new int[] {v[0], a},
        inject(Arrays.copyOfRange(v, 1, v.length), b, a));
}

Arrays.copyOfRange gives us a convenient way to create an array which is just the "tail" of the current array. Calling this with:

inject(new int[] {1, 5, 6, 8}, 0, 1));

returns the expected:

{1, 0, 5, 1, 6, 0, 8}

You can make it cleaner and clearer with a couple of helper methods:

int[] tail(int[] v) {
    return Arrays.copyOfRange(v, 1, v.length);
}

int[] arrayOf(int... ints) {
    return ints;
}

Then the recursive method becomes:

int[] inject(int[] v, int a, int b) {
    if (v.length < 2) return v;
    return concat(arrayOf(v[0], a), inject(tail(v), b, a));
}