Java, recursively reverse an array

Question

I haven't found anything with the specific needs of my function to do this, yes, it is for homework.

So I have:

public void reverseArray(int[] x) {

}

Precondition: x.length > 0

The fact that I can't have the function return anything, and the only argument is an array is leaving me stumped.

I've tried using loops along with the recursion, but everything I've tried seems to end up with infinite instances of the function being made.

I've gotten an idea/suggestion to use another function along with this one, but, how to use the original recursively is beyond me at the moment.

Any help is appreciated.

Answer 1

If I were coding this, I would create a temporary array (maybe with one element removed?) for the recursive call and copy elements back into the original array before returning from the function. You will also need to find a base case to terminate the recursion.

Answer 2

Here is the main method:

package main;

public class Main {
    public static void main(String[] args) {
        StringOps ops = new StringOps();
        String string = "Arjun";
        // reversing the string recrusively
        System.out.println(ops.reverseRecursively(string.toCharArray(), 0));
    }
}

and here is the recursive function:

package main;

public class StringOps {
    public char[] reverseRecursively(char[] array, int i) {
        char[] empty = new char[0];
        if (array.length < 1) {
            System.out.println("you entered empty string");
            return empty;
        }
        char temp;
        temp = array[i];
        array[i] = array[array.length - 1 - i];
        array[array.length - 1 - i] = temp;
        i++;

        if (i >= array.length - 1 - i) {
            return array;
        } else {
            reverseRecursively(array, i);
            return array;
        }

    }

}

Answer 3

//We are just doing an operation here and calling a helper method.

public void reverseArray(int[] nums){
  int[] hold = new int[nums.length]; //just so it will take this argument
  int[] reversed = recurReverseArray(nums, hold, nums.length - 1, 0);
  nums = reversed; //not returning just changing nums to be reversed.
}
public int[] recurReverseArray(int[] nums, int[] reverse, int end, int start){
  if(end == 0 && start == nums.length - 1){
  reverse[start] = nums[end];
  return reverse; //the way out.
  }
  reverse[start] = nums[end];
  return recurReverseArray(nums, reverse, end - 1, start + 1);
}

Answer 4

Because this is your homework, I suggest an example :

Given sequence : 1 2 3 4 5 6 7 8 9 10

You can change to : 10 2 3 4 5 6 7 8 9 1

After that: 10 9 3 4 5 6 7 8 2 1

.....

As you see, step by step, the sequence is "better" and the problem is "smaller". So, the problem you should solve to complete is :

1) How to apply recursive call for this method. for the original, the method is : reverse(int[] a). so, after first step, you should create array b from a[2] --> a[n-1]. and using reverse(int[] b)`.

2) after reverse b, what should we do to reverse a ? Assign values of b again back to a.

3) stop condition : what stop condition ? You see that elements of array b less than elements of array a. So, to which step, we should stop ?

Hope this help :)

Answer 5

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

void reverse(int[] x, int i, int j){
    if(i<j){//Swap
       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 6

public class RecursiveArray {


   public static int[] backWardArray(int[] arr, int start, int end) {

       if (start < end) {
           int temp = arr[start];
           arr[start] = arr[end];
           arr[end] = temp;
           backWardArray(arr, start + 1, end - 1);
       }
       return arr;
   }

    public static void main(String[] args) {
        int [] arr = {12,4,6,8,9,2,1,0};
    int [] reversedArray= backWardArray(arr, 0, arr.length-1);
    //loop through the reversed array
        for (int i: reversedArray) {
            System.out.println(i);
        }
    }

    public RecursiveArray() {
    }
}