Question

Using Java solve recursively without the use of loops or modifying the method signatures.

/**

* Given a sorted input array a, return a sorted array of size a.length + 1,

* consisting of all elements of array a and integer i.

*

* @param a an array that is sorted in a non-descending order

* @param i an integer

* @return a sorted array of size a.length + 1, consisting of all elements of

* array a and integer i. e.g., insertIntoSortedArray({1, 2, 4, 5}, 3)

* returns a sorted array {1, 2, 3, 4, 5}.

*

* <b>You are forbidden to use the insertIntoSortedList method below to

* solve this problem.</b>

*

* Requirement: You are required to implement all methods recursively.

* You receive a zero if there is any occurrence of a loop (e.g., for,

* while).

*/

public int[] insertIntoSortedArray(int[] a, int i) {

/*

* Your Task: Define a recursive method yourself and use it here.

*/

return null;

}

Answer 1

import java.io.IOException;

public class InsertIntoSortedArrayUsingRecursion {

public static int[] insertIntoSortedArray(int[] a, int i) {

int [] arr=new int[a.length+1];

insert(arr, a, i ,0, false);

for(Integer an: arr) {

System.out.print(an+" ");

}

return arr;

}

public static void insert(int[] arr,int[] a, int i, int index, boolean found) {

if(index == arr.length -1) {

if(found) {

return ;

}else {

arr[index] = i;

return;

}

}

int newValue = index;

if( i <= a[index] && !found) {

arr[index] = i;

found = true;

}else {

if(found) {

arr[index+1] = a[index];

}else {

arr[index] = a[index];

}

newValue++;

}

insert(arr, a, i ,newValue, found);

}

public static void main(String[] args) throws IOException {

int[] a = {1, 2,4, 5};

insertIntoSortedArray(a, 3);

}

}

output is: