how to write a recursive method in java to reverse the values stored in an integer array?

Question

I'm having hard time figuring how to reverse the values that stored in an integer array this my code:

private static void randomizeArray (int[] arr, int upperLimit)

{
// Loop to generate and store in array random numbers from 1 to upperLimit

    Random rand = new Random();

    for (int i = 0; i < arr.length; i++)

        arr[i] = rand.nextInt(upperLimit) + 1;

}

private static void printArray (String heading, int[] arr)

{

    // Loop to print array numbers

    System.out.print(heading + ": [");

    for (int i = 0; i < arr.length; i++)

    System.out.printf("%3d", arr[i]);

    System.out.println("]");

}

private static int[] reverseArray (int[] arr)

{


}

}

Answer 1

Do something like this:

 void reverseArray(int[] arr) {
   reverse(arr, 0, arr.length - 1);
}

void reverse(int[] arr, int s, int e) {
    if(s < e) {
       /* swap start and end index elements */
       int tmp = arr[s];
       arr[s] = arr[e];
       arr[e] = tmp;
       reverse(arr, ++s, --e);
    }   
}

Recursive, doesn't require any extra buffer and runs in O(n).

An iterative version can be something like this:

int[] reverseArray(int[] arr) {
    int startIndex = 0, endIndex = arr.length - 1;
    for (int i=startIndex; i<endIndex/2; i++) {
        int tmp = arr[i];
        arr[i] = arr[endIndex-i];
        arr[endIndex-i] = tmp;
    }
    return arr;
}

Answer 2

private static int[] reverseArray (int[] arr)

{
    if(arr.length == 1){
        return arr;
    }
    else{
        int temp = arr[0];
        int tempArr[] = new int[arr.length-1];
        System.arraycopy(arr, 1, tempArr, 0, tempArr.length);
        tempArr = reverseArray(tempArr);
        System.arraycopy(tempArr, 0, arr, 0, tempArr.length);
        arr[arr.length-1] = temp;
        return arr;
    }
}

Answer 3

To create a recursive algorithm, you need two things.

Base Case

What's the smallest case you can reasonably encounter, and what should the result be?

The empty array is its own reverse. Can't get any smaller than that.

rev( [] ) = []

Depending on the next step, you might also need to define the singleton case as a base case:

rev( [ r ] ) = [ r ]

Inductive Step

Given a function rev_n that works for any input of "size" <= n, for some suitable definition of "size", can you use that function to produce the result for any input of "size" n + 1?

rev( [ r₁, ..., r_n, r_n+1 ] ) = [ r_n+1 ] ++ rev_n( [ r₁, ..., r_n ] )

or (assuming the singleton case is also defined as a base case)

rev( [ r₁, ..., r_n, r_n+1 ] ) = [ r_n+1 ] ++ rev_n( [ r₂, ... r_n ] ) ++ [ r₁ ]

Answer 4

In order to write a recursive program that reverses an array, you need to :

a. swap the first element with the last element of the array

b. Call the above with the sub array without the first and the last elements

c. stop calling a - if there is no element left to swap

Consider the following code

void reverseArray(int arr[], int start, int end){
   int temp;
   if(start >= end)
     return;
   temp = arr[start];   
   arr[start] = arr[end];
   arr[end] = temp;
   rvereseArray(arr, start+1, end-1);   
} 

This code will not exactly fit into your template, you need to tweak it to return the int[]

Answer 5

There are many ways to do this. This would be really easy to do with a Stack, but there is another easy way to do it as well by storing the values in a temporary array. Basically you use j as a pointer to the last spot in the arr array and load whatever value that is into the front of the tempArray. After each iteration of the loop, we decrement j and increment i, changing their pointers to continue placing the values of arr in reverse order into tempArray. Hope that helps.

private static int[] reverseArray (int[] arr)
{
    int[] tempArray = new int[arr.length];
    int j = arr.length-1;
    for(int i = 0; i < arr.length; i++){
        tempArray[i] = arr[j];
        j--;
    }
    return tempArray;
}