Combine 2 arrays using recursion

Question

How do I combine 2 int arrays using recursion? It has to be from small to big. Right now it only combines the 5 first values of 20.

I want to combine these 2 arrays by sending both arrays to the function and 1 empty array (The new sorted one). Once in the function it needs to get the smallest number of both arrays. So for example the 1 in array A is smaller then the 2 array B. And then that value needs to be added to the new sorted array. And that until every number is sorted into the new array.

The result of the new array should be :

[ 1, 2, 3, 4, 5, 8, 13, 16, 21, 32, 34, 55, 64, 89, 128, 256, 512, 1024, , 2048, 5099]

I know there are better ways to do this but this is for a school project to learn recursion

This is my code : (Findme is the name of the class the function is in)

public int[] combineArray(int[] a, int[] b, int[] c, int i, int j, int x){
        if(a[i] > a.length || b[j] > b.length ){
            return c;
        }
        if(a[i] < b[j]){
            c[x] = a[i];
            combineArray(a, b, c, i + 1, j, x + 1);
        }
        if(a[i] > b[j]){
            c[x] = b[j];
            combineArray(a, b, c, i, j + 1, x + 1);
        }
        return c;
    }
 public static void main(String [] args)
    {
        findMe find = new findMe();
        int[] a = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        int[] b = {4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
        int[] c = new int[20];
        int[] x = find.combineArray(a, b, c,0 , 0, 0);
        for(int i = 0; i < find.combineArray(a, b, c,0 , 0, 0).length; i++){
            System.out.println("On position : " + i + " is value " + x[i]);
        }

    }

Marius Manastireanu · Answer

Your stopping condition is faulty.

First of all you compare a certain value of array a and b at position i/j with the length of array a and b, you should check for the index itself.

Secondly, there is only one final step where you should stop - which is both arrays a and b were fully processed (you are currently checking with or).

Based on your current implementation your method should look something like this:

    public int[] combineArray(int[] a, int[] b, int[] c, int i, int j, int x){
        if (i >= a.length && j >= b.length) {
            // only if both arrays are processed stop and return c
            return c;
        } else if (i >= a.length) {
            // we finished with array A, process array B
            c[x] = b[j];
            combineArray(a, b, c, i, j + 1, x + 1);
        } else if (j >= b.length) {
            // we finished with array B, process array A
            c[x] = a[i];
            combineArray(a, b, c, i + 1, j, x + 1);
        } else {
            // both arrays still have elements
            if (a[i] < b[j]) {
                c[x] = a[i];
                combineArray(a, b, c, i + 1, j, x + 1);
            } else {
                c[x] = b[j];
                combineArray(a, b, c, i, j + 1, x + 1);
            }
        }
        return c;
    }

Last but not least, when you print the array you would want to iterate over the array c itself, not call again the find.combineArray method, something like

        for(int i = 0; i < x.length; i++){
            System.out.println("On position : " + i + " is value " + x[i]);
        }

ILikeTrains · Answer

Important: There was a duplicated 8, one 8 in array a and one 8 in array b, yet in the array displaying the results array, there are no two 8´s. Also you did not mention how to handle that, so I think this might be a typo, because the sum of elements of array a and b is one less than the size of the result array c. Thats why I removed one 8. But it would also work with both 8´s.

Try this:

    public void combineArray(int[] a, int[] b, int[] c, int i, int j, int x) {
        if (i == a.length && j == b.length) {
            return;
        }

        if (i == a.length) {
            c[x] = b[j];
            combineArray(a, b, c, i, j + 1, x + 1);
            return;
        }

        if (j == b.length) {
            c[x] = a[i];
            combineArray(a, b, c, i + 1, j, x + 1);
            return;
        }

        if(a[i] <= b[j]) {
            c[x] = a[i];
            combineArray(a, b, c, i + 1, j, x + 1);
            return;
        }

        if(a[i] > b[j]) {
            c[x] = b[j];
            combineArray(a, b, c, i, j + 1, x + 1);
            return;
        }
    }
    
    public static void main(String [] args) {
        FindMe find = new FindMe();
        int[] a = {1, 2, 3, 5, 13, 21, 34, 55, 89};
        int[] b = {4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
        int[] c = new int[a.length + b.length];
        find.combineArray(a, b, c, 0, 0, 0);
        for (int i = 0; i < c.length; i++) {
            System.out.println("On position : " + i + " is value " + c[i]);
        }
    }

Here are some points to mention:

You are calling the method combineArray() every iteration int the for-loop. Don't do that, just take the length of the array with the results.
you dont need that x array, you are already writing all the results into the c array.
Therefor you also dont need to return some form of array from the method.
Don´t just a literal to instanciate the c array. The length of the c array is the sum of the lengths of the a and b arrays, which you want to combine.
Make sure to check the indexes i, j and x before using them for retrieving values from the arrays. Otherwise you might run into OutOfIndexExceptions.
Be carefully with formatting your code and values.

Combine 2 arrays using recursion

2 Answers