Home > Mobile >  Recursively merging two arrays into one large array
Recursively merging two arrays into one large array

Time:04-16

So this is the prompt: Given two arrays that are full of integers, recursively merge these two arrays into one large array.

This is my code(the method headers cannot be changed):

public class Problem6 {
public void mergeArrays(int[] arrayOne, int[] arrayTwo, int[] mergedArray) { 
    int i = 0, j = 0, k = 0;

    if(k%2 == 0) {
        mergedArray[k] = arrayOne[i];
        i  ;
    }
    
    else {
        mergedArray[k] = arrayTwo[j];
        j  ;
    }
    
    k  ;
    mergeArrays(arrayOne, arrayTwo, mergedArray);
}

public static void main(String[] args) {
    
    
    int[] arrayOne = {0, 2, 4, 6, 8, 10};
    int[] arrayTwo = {1, 3, 5, 7, 9};
    
    }
}

I'm really struggling with making this code work...I'm not sure what to put in the main method or if my mergeArrays method is even correct. Can someone help me out?

CodePudding user response:

The trick is that you can create additional methods outside of the interface you were given:

public class RecursiveMerge {
public void mergeArrays(int[] arrayOne, int[] arrayTwo, int[] mergedArray) {
    //call the internal recursive function 
    mergeArraysInternal(arrayOne, arrayTwo, 0, 0, mergedArray);
}

private void mergeArraysInternal(int[] arrayOne, int[] arrayTwo, int idxA, int idxB, int[] mergedArray) {
    int idx = idxA idxB; //this will be the index of the mergedArray to receive a value
    if (idxA >= arrayOne.length) { //test if you're outside the bounds
        if (idxB >= arrayTwo.length) {
            return;
        }
        
        mergedArray[idx] = arrayTwo[idxB  ];
    } else if (idxB >= arrayTwo.length) { //more bounds testing
        mergedArray[idx] = arrayOne[idxA  ];
    } else  if (arrayOne[idxA] <= arrayTwo[idxB]) { //test for differences
        mergedArray[idx] = arrayOne[idxA  ];
    } else {
        mergedArray[idx] = arrayTwo[idxB  ];
    }
    //recurse
    mergeArraysInternal(arrayOne, arrayTwo, idxA, idxB, mergedArray);
}

public static void main(String[] args) {
    
    
    int[] arrayOne = {0, 2, 4, 6, 8, 10};
    int[] arrayTwo = {1, 3, 5, 7, 9};
    int[] mergeArray = new int[arrayOne.length   arrayTwo.length];
    
   new RecursiveMerge().mergeArrays(arrayOne, arrayTwo, mergeArray);
   
   System.out.println(Arrays.toString(mergeArray));
}

}

CodePudding user response:

Recursive Functions have a flow that goes like this

DoSomeWork

If work is done, return answer Otherwise, call myself and change the input

For example, let's say I have an integer from 0-100, and I want to reclusively check how many numbers from 100 my number is

public int DistanceFromLimit(int start,int steps){
    if(start==100){
        return steps;
    }
    else{
        return DistanceFromLimit(start 1,steps 1);
    }

   
 public static void main(String[] args) {
    DistanceFromLimit(75,0);
 }

When my program starts, steps is 0 and start is 75. My program checks start and sees that 75 is not 100. So it then calls itself with start at 76 and steps at 1. The 2nd layer of the program sees that 76 is not 100, so it calls itself with start as 77 and steps at 2.

This will keep going until steps finally is 100.

So you need to provide work and a condition of when that work is done. If the work is done, return some answer. If the work is not done, then call the same function, changing the input to represent the work already done.

  • Related