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.