Write a recursive method called which takes in an array of integers and returns said array in reversed sorted order

Question

I have a programming exam in a few days so I'm doing some exercises just to practice. However, I've been stuck with this problem and I started to doubt if it's possible to do it. Write a recursive method called arrayReverse which takes in an array of integers and returns said array in reversed sorted order. So an example would be:

input: [1,2,3]    
output:[3,2,1]

I wasn't able to solve it. My intuition was to take the last element of the array, put it at the beginning, i,e: index[0] and then recursively call the rest of the array but then taking the new last element and put it on index[1]. Unfortunately, the implementation was harder than I thought but I (for the sake of trying) edited the question in a way that it accepts 2 arrays and this was my code:

import java.util.Arrays;

class Test {

  int[] arrayReverse(int[] m, int[] mReverse) {
    if (m.length == 1) {
        mReverse[mReverse.length - 1] = m[0];
        return mReverse;
    } else {
        int lastNum = m[m.length - 1];
        mReverse[mReverse.length - m.length] = lastNum;
        int[] arrayMinusOne = cropArray(m);
        return arrayReverse(arrayMinusOne, mReverse);
    }
}

int[] cropArray(int[] m) {
    int[] mCropped = new int[m.length - 1];
    for (int i = 0; i < m.length - 1; i++) {
        mCropped[i] = m[i];
    }
    return mCropped;
}

}
  void demo() {

    int[] helpTest4 = new int[]{1, 2, 3};
    int[] emptyArray = new int[helpTest4.length];

    int[] test4 = arrayReverse(helpTest4, emptyArray);
    System.out.println(Arrays.toString(test4));


}

public static void main(String[] args) {
    new Test().demo();
}
}

It works perfectly but I'm not satisfied with the result because of two reasons:

1. I wasn't able to do it completely recursive. I used a for loop in cropArray.
2. I couldn't do it on one array.

How can this be done?

Answer 1

Option1: Using only one parameter (array) in the recursive function

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class MyClass {
     public static void main(String[] args) {

        int[] arr = {1,2,3,4,5};
        int[] reversed = reverseArray(arr);
        System.out.println(Arrays.toString(reversed));
    }

    public static int[] reverseArray(int[] arr)
    {
        if (arr.length == 0)
            return arr;

        // remove first element   
        int first = arr[0];
        int[] list = Arrays.copyOfRange(arr, 1, arr.length);

        //Calling Function Recursively get reversed array
        int[] returnArr = reverseArray(list);

        //Add original first to the last of the arrayToReturn
        returnArr = Arrays.copyOf(returnArr, returnArr.length + 1);
        returnArr[returnArr.length - 1] = first;

        return  returnArr;
    }
}

Option2:

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

void reverse(int[] x, int i, int j){
    if(i<j){//Swap ith with jth element where i and j are equidistant from ends
       int tmp = x[i];
       x[i] = x[j];
       x[j] = tmp;
       reverse(x, ++i, --j);//Recursive
    }   
}

Test:

int[] s = new int[]{1,2,3,4,5};
reverseArray(s);
System.out.println(Arrays.toString(s));//"5,4,3,2,1"

Recursive, O(n), no temporary Array needed.

Answer 2

Please try the code below:

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
         Scanner sc  = new Scanner(System.in);
        
        int n = sc.nextInt();
        int arr[]= new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sc.nextInt();
        }
        Printsum(arr,0);
     }
     
     public static void Printsum(int arr[], int idx)
     {
         if(idx == arr.length)
         return ;
         
         Printsum(arr,idx+1);
         System.out.println(arr[idx]);
     }
}

Answer 3

I don't think this is a particularly good question - there is obviously a direct and clear way to do it without recursion; so the question does little to demonstrate any useful knowledge of recursion.

That said I believe the algorithm they were seeking uses the facts that:

a) reversing a 1 length array is trivial

b) you can reverse an n length array by appending the first element to the reverse the the last n-1 elements.

So code for this solution will look much simpler that what you currently have.

Answer 4

Ruby:

def reverse(a)
  if a.empty?
    return []
  else
    return [a.last] + reverse(a[0..-2]) 
  end
end

a = [1, 2, 3]

reverse(a)

Answer 5

Taking the request literally, I have come out with a solution which only needs ONE recursive function with just ONE input/output parameter:

public static void arrayReverse(int[] input)
{
    if (input.length > 0)
    {
        // Store locally the fist element:
        int firstElement=input[0];

        // Creates a sub-array and reverses it:
        int[] input2=new int[input.length - 1];
        System.arraycopy(input, 1, input2, 0, input2.length);
        arrayReverse(input2);

        // Copies back the reversed array into the current array:
        System.arraycopy(input2, 0, input, 0, input2.length);

        // Puts the stored fist element in the last position:
        input[input.length - 1]=firstElement;
    }
}

This solution is based upon a stack structure, for which it takes advantage of the machine calling stack at runtime, where the local values are stored while the function is executing.

• The base case of this recursion is, of corse, the empty array.
• In the generic case, the function stores locally the first element, then re-invokes itself recursively to reverse the rest of the array, and last, puts back the first element in the last position.