Can't change variable while doing recursion

Question

public static void main(String[] args) {
    int[] a = { 1, 2, 3, 4, 5 };
    int[] b = new int[5];
    rekursiq(a, b, 0, 0, 1);
}

static void rekursiq(int[] a, int[] b, int index, int start, int check) {
    if (index == b.length){
        System.out.println(java.util.Arrays.toString(b));
    } else {
        for (int i = start; i < a.length; i++) {
            b[index] = a[i];
            rekursiq(a, b, index + 1, i + 1, check + 1);
        }
    }
}

Now my question is: Instead of b.length in the recursion bottom I want to place an int check, and make check go +1 on every going there, and do something. while (check < b.length) go the if statement, else return; but I can't seem to 1) increase the value properly and 2) make this while correctly. I don't know why.

I think my best try was

static void rekursiq(int[] a, int[] b, int index, int start, int check) {
    if (check > b.length) {
        return;
    } else {
        if (index == check) {
            System.out.println(java.util.Arrays.toString(b));
        } else {
            for (int i = start; i < a.length; i++) {
                b[index] = a[i];
                rekursiq(a, b, index + 1, i + 1, check + 1);
            }
        }
    }
}

But it did not work, and I hope some one of you can tell me why and how to fix it.

Answer 1

The value of check does increase when the method is called recursively. However, the problem you have is independent of check.

The Problem

Let me start by repeating what abhishrp already briefly mentioned: In this particular case, you want to either use a loop to iterate over all elements in the array, or recursion, but not use a loop inside of your recursive method. The reason is the following: At each step in the recursion, you look at exactly one element: the element at position index.

The Solution

So, how would you recursively copy an array? Let us assume you have a source array (in your code a) and an empty destination array (in your code b). Now, we know how to copy a single element of the array, namely destination[index] = source[index], and we can imagine copying the array as copying the first element, and then copying the subarray starting at the second element. Note that knowing how to copy a single element in an array implies knowing how to copy an array containing only one element.

This leads us to the following recursion, which we will turn to code shortly after:

• if the given index dereferences the last element in the array, then copy this last element.
• otherwise, copy the element at the current index, and copy the subarray starting at the next index.

Or expressed in Java:

static void copyValuesFromSourceToDestinationStartingAtIndex(int[] source, int[] destination, int index) {
    if (isIndexOfLastElementInArray(index, destination)) {
        destination[index] = source[index];
    } else {
        destination[index] = source[index];
        copyValuesFromSourceToDestinationStartingAtIndex(source, destination, index + 1);
    }
}

static boolean isIndexOfLastElementInArray(int index, int[] array){
    return index == array.length - 1;
}

Note that you have too many parameters in your code: The parameter check is really just index, as you want to check whether the index is still inside the bounds of the array. I don't really know what you intended to do with the variable start though - seems like somehow you got confused there because of the loop.

---

Sidenote

Also, a small justification on why the true-branch of the if-statement in the above code does copy the last element instead of returning nothing if the index is out of bounds as in your code. It's perfectly reasonable to do it like you did. The argument "We trivially know how to copy an empty array" just didn't seem as natural as "knowing how to copy a single element implies knowing how to copy an array consisting of a single element". I encourage you however to adjust the code to "copy an empty array" as a base-case, because it removes the duplication, and more importantly, allows you to copy empty arrays (for which the above implementation would fail horribly).

---

Code

I also tried to give a comparison between the iterative and the recursive approach:

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5};
    int[] copyOfAUsingIteration = copyArrayUsingIteration(a);
    int[] copyOfAUsingRecursion = copyArrayUsingRecursion(a);
    assert(Arrays.equals(copyOfAUsingIteration, copyOfAUsingRecursion));
    assert(copyOfAUsingIteration != a);
    assert(copyOfAUsingRecursion != a); 
    System.out.println(java.util.Arrays.toString(copyOfAUsingIteration));
    System.out.println(java.util.Arrays.toString(copyOfAUsingRecursion));
}

static int[] copyArrayUsingIteration(int[] arrayToCopy) {
    int[] result = new int[arrayToCopy.length];
    for(int index = 0; index < result.length; index++){
        result[index] = arrayToCopy[index];
    }
    return result;
}

static int[] copyArrayUsingRecursion(int[] arrayToCopy){
    if (arrayToCopy.length == 0){
        return new int[0];
    } else {
        int[] result = new int[arrayToCopy.length];
        copyValuesFromSourceToDestinationStartingAtIndex(arrayToCopy, result, 0);
        return result;
    }
}

static void copyValuesFromSourceToDestinationStartingAtIndex(int[] source, int[] destination, int index) {
    if (isIndexOfLastElementInArray(index, destination)) {
        destination[index] = source[index];
    } else {
        destination[index] = source[index];
        copyValuesFromSourceToDestinationStartingAtIndex(source, destination, index + 1);
    }
}

static boolean isIndexOfLastElementInArray(int index, int[] array){
    return index == array.length - 1;
}

Answer 2

To copy one array to another you can use either iteration or recursion. There is no need to do both. By this I mean there is no need for the for loop inside the rekursiq method.