14

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.

Improve this question
10
  • You can change the data inside the array on your method. There's nothing wrong reversing an array in a method that returns nothing. It would be good to post your idea and we gladly give you advices (not code) from there. Commented Oct 31, 2012 at 1:49
  • By the way, can you add another parameter to your reverseArray method? Commented Oct 31, 2012 at 1:50
  • We cannot add another parameter, if that was so, I know how I would do it. And yes, helper methods were mentioned as a viable option, I'm just not sure how that would be implemented. Commented Oct 31, 2012 at 1:56
  • 2
    @HotLicks, extra parameters are forbidden, I think. Commented Oct 31, 2012 at 2:00
  • 2
    If you can't have any extra parameters (and you can't have extra elements in the array to act like parameters) and you can't create copies of the array then you can't do it. If you can make copies (and use System.arraycopy) then you can do it, by passing shorter and shorter copies of the array. Commented Oct 31, 2012 at 2:03

14 Answers 14

Reset to default
18 
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

The above doesn't meet the restriction (perceived by some) that you can't have any extra arguments. But it's the most obvious solution to me (and the one I suggested above).
8

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.

Improve this answer

5 Comments

+1 The temporary array that is being passed to reverseArray will be one element shorter every step (so that recursion terminates after N steps).
@Thilo I decided my original answer had too many details, so I rewrote it.
I had this as an idea, I just wasn't sure how to implement it earlier, I think I may have it figured out now. Pass in a stripped down array (first and last elements removed) into a new instance of the function, until the length is 2, switch them, (if length == 1, do nothing), and then from thereon, on each end of an instance, tack on the removed elements, but switched?
This put me on the right path without telling me exactly what to do, much appreciated.
@dabbertorres I only had in mind removing either the first or last element. I like your idea to remove both and switch them.
7

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 :)

Improve this answer

1 Comment

I have edited again my solution to not use helper function. If we use helper function, it will be better. But, I dont think your teacher will like this :)
2

Calling reverseArray(0, n, arr) here n is length of array

public void reverseArray(int i, int n, int [] arr)
{
   if(i==n)
   {
     return ;
   } 
   else
   {
     reverseArray(i+1, n, arr);
     System.out.println(arr.at(i));
   }
}
Improve this answer

Comments

2 
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() {
    }
}
Improve this answer

Comments

1

Try something as below:

public void reverseArray(int[] x) {
    if(x.length ==2){
      //if two elements, swap them
      int first = x[0];
      x[0] = x[1];
      x[1] = first;
    }else if(x.length > 2){
      //swap first and last
      int first = x[0];
      x[0]= x[x.length-1];
      x[x.length-1] = first;
      //create a copy of middle elements
      int [] copy = new int[x.length-2];
      System.arraycopy( x, 1, copy, 0, x.length-2);
      //recursive call for middle elements
      reverseArray(copy);
      //place the reversed elements back in the original array
      System.arraycopy( copy, 0, x, 1, copy.length);
    }
}
Improve this answer

2 Comments

Essentially the same as the proposal by @Pogo.
Although it works, this kind of reversing is horribly inefficient as many sub-arrays are being created and read. This makes the runtime from 0(n) to 0(n^2)!
0

//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);
}
Improve this answer

Comments

0

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;
        }

    }

}
Improve this answer

Comments

0 
public class FunWithAlgorthims {


public static void main(final String[] args) {

    String[] array = {"a", "b", "c", "d"};
    printArray(array);
    revereArrayRecusrive(array, 0);
    printArray(array);
}


public static void revereArrayRecusrive(final String[] array, int startPointer) {
    if (startPointer >= (array.length / 2)) {
        return;
    }
    String temp = array[startPointer];
    array[startPointer] = array[array.length - 1 - startPointer];
    array[array.length - 1 - startPointer] = temp;
    revereArrayRecusrive(array, ++startPointer);
}

public static void printArray(final String[] array) {
    Arrays.stream(array).forEach(a -> System.out.print(a + " "));
    System.out.println();
}

}

Improve this answer

Comments

0

This is probably the easiest way, not the fastest, but probably the easiest.

A whole program would look something like this:

public static void main(String [] args)
{
    BackwardsArray back = new BackwardsArray();
}

public BackwardsArray()
{
    int [] a = {1,2,3,4,5,6,7,8,9};
    printBackwards(a);
}

void printBackwards( int [] b)
{
    print(b,b.length-1);
}

void print(int [] b, int pos)
{
    System.out.println(b[pos]); // prints last item
    if(pos != 0)
    {
        print(b,pos-1);
    }
}

Hope it helps!

Improve this answer

Comments

0 
private static void reversePrint(int[] numbers)
{
    if(numbers.length==0) {
        return;
    }
    int[] a = new int[numbers.length -1];
    for(int i =0;i<numbers.length-1;i++) {
        a[i] = numbers[i+1];
    }
    reversePrint(a);
    System.out.println(numbers[0]+" ");

}
Improve this answer

Comments

0

Simple solution:

int[] arr = { 1, 3, 4, 56, 6 };
int[] ans = new int[arr.length];
int num = arr.length-1;
for (int i = 0; i < arr.length; i++) {
   ans[i] = arr[num];
   System.out.println(ans[i]);
   num--;
}
Improve this answer

Comments

-1

psuedo code

function revarray(a[1...n])
  if a.length == 1 or a.length == 0
    do nothing 
  # return a
  else
     swap a[1] and a[n]
     revarray(a[2...n-1])
  # return a (The function will not return anything but the contents of a are changed)
Improve this answer

2 Comments

This is one obvious solution, but in Java it requires constructing a new array and copying to/from it with System.arraycopy, so a few lines more complex than the pseudocode suggests.
Why is this answer marked down? It's the same as Yogendra Singh's (later) suggestion that's gotten +2 so far.
-1

Since there's been no statement that loops cannot be used:

void reverseArray(int[] x) {
    if (x != null) {
        for (int i = 0; i < length.x / 2; i++) {
            int j = (length.x - 1) - i;
            int temp = x[i];
            x[i] = x[j];
            x[j] = temp;
         }
         reverseArray(null);
     }
}

Probably the fastest of the lot.

Improve this answer

4 Comments

@NullUserException -- When I was in college using a computer was sometimes considered cheating. Whatever works!
Haha, yes, based off what I wrote, this is acceptable, but the actual problem does say no loops. If only...
It's recursive. See the reverseArray(null); call?
The method call is recursive, but the actual operation is not.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.