1

supposed to reverse an array of strings recursively.

having trouble implementing this. if i was using a for loop i would just start it at the end of the array and print out the array starting with the last element and ending with the first.

I'm not too sure how to do it recursively. i was thinking about using a swap but that idea sort of fizzled when i couldnt figure out how to change the elements that i was swapping.

any ideas or a push in the right direction would be appreciated.

this is what icame up with so far. i know its wrong, i get an error out of bounds exception which im not sure how to fix. I think im not swapping the first and last correctly. but am i getting the right idea?

this is what i came up with. a is an array. its inside a class.

// reverse an array 

public void rev() 
{
    rev(0,a.length-1);
} 

private void rev(int first, int last)
{
if(last == 0)
{
//do nothing
}

else
{
while(first != last)
{
int temp = first;
first = last;
last = temp;


System.out.print(" " + a[first]);
rev((first + 1), (last - 1));
}

}
}

made some changes and it reverses the last 3 elements but the it repeats the second element. i have no if statement that controls when it runs so shouldnt it run until left = right?

this is what i changed it to

// reverse an array 
public void rev() 
{
    rev(0,a.length-1);
} 

private void rev(int first, int last)
{
    if(last == 0)
    {
    //do nothing
    }

    else
    {


    String temp = a[first];
    a[first] = a[last];
    a[last] = temp;

    System.out.print(" " + a[first]);
    rev(first+ 1, last-1);

    }
}
Improve this question
8
  • keep two indexes (first, last), swap these postitions and increase start, and decrease last until they are the same element or only have one element in between... Commented Sep 24, 2011 at 3:20
  • 4
    Is this an interview question or a homework assignment? Commented Sep 24, 2011 at 3:23
  • Well, first and foremost: what is does the signature of the recursive function need to look like? Since this is homework, I suspect there is a specific "template" and this will heavily influence the advice given. Java, unfortunately, is a horrid language to teach this sort of recursion in :-/ Commented Sep 24, 2011 at 4:25
  • what do you mean by the "signature of the recursive function"? is that the same as the call to the recursive method inside of it? Commented Sep 24, 2011 at 4:26
  • Well, a signature might be: String[] reverseString(String[] in) -- it is the name, return, and input parameter(s). Commented Sep 24, 2011 at 4:31

6 Answers 6

Reset to default
4

The trick with recursion is to try and think of the problem in terms of a base case and then a way to reduce everything to that base case.

So, if you're trying to reverse a list then you can think of it like this:

  1. The reverse of a list of size 1 is that list.
  2. For a list of size > 1 then the first element in the output list will be the last element of the input list.
  3. The rest of the output list will be the reverse of the input list, minus the last element.

You now have your recursive definition.

Hope that helps.

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

4 Comments

this is what i came up with. i know its wrong, i get an error out of bounds exception which is because im switching first and last and then printing out first but after one run first gets subtracted.// reverse an array public void rev() { rev(0,a.length-1); } private void rev(int first, int last) { if(last == 0) { //do nothing } else { while(first != last) { int temp = first; first = last; last = temp; System.out.print(" " + a[first]); rev((first + 1), (last - 1)); } } }
Unfortunately Java's lack of sane list (as in "cons list") type makes it much harder to implement it like this than a myriad of other languages... :-/ The arrays don't help either.
@user945547: Can you update your question with your code? It's pretty hard to read code in a comment line because it's unformatted.
i did, sorry about that. i noticed that it wouldnt format correctly
2

the while loop is too much, since you are using recursion anyway, try it like this

private void rev(int first, int last)
{
   if(first < last)
   {
      var temp = a[first];
      a[first] = a[last];
      a[last]  = temp;
      rev(first + 1, last - 1);
   }
}
Improve this answer

Comments

1

I always like having a simple public method that calls the private recursive one. That way from other places in your code you just give it the array, and don't have to worry about the other arguments. Also, this catches empty arrays, but you would still need to check for null at some point near the start. Maybe throw an exception in the public method if the array is null?

public String[] reverseArray(String[] theArray) {
    this.reverseArrayWorker(theArray, 0, theArray.length -1);
}

private String[] reverseArrayWorker(String[] theArray, int left, int right) {
    // Check your base cases first
    if (theArray.length <= 1) {
        // Array is one element or empty
        return theArray;
    } else if (left - right <= 0) {
        // If there are an odd # of items in the list you hit the center
        // If there are an even number your indexes past each other
        return theArray;
    }
    // Make the recursive call
    this.reverseArrayWorker(theArray, left + 1, right - 1);
    // Switch the two elements at this level
    String temp = theArray[left];
    theArray[left] = theArray[right];
    theArray[right] = temp;
    // Return the array up a level
    return theArray;
}
Improve this answer

3 Comments

did you just assign temp to theArray[left] to empty up that element?
@alexthefourth: oopss, typo, I should have set theArray[right] like this... theArray[right] = temp; you need the third temp variable to hold the value of the first you one you replace. Hopefully it is clearer with the edit.
i do not see the need to return the array, since you are using the same reference to it anyways.
0 
public int[] reverse(int[] returnMe, int[] original, int curPos){
    if (original.length == 1){
        return original;
    }else{
        if (curPos < original.length){
            returnMe[curPos] = original[original.length - 1 - curPos];
            reverse(returnMe, original, curPos + 1);
        }else{
            return returnMe;
        }
    }
}
Improve this answer

3 Comments

That's not really in the spirit of recursion. Generally a recursive solution does not use any data that isn't on the stack, i.e. it takes all its input as arguments, returns a value, and has no side effects.
@Cameron Skinner However, that makes this problem quite difficult to perform in Java on int[] input... Integer[] would at least allow the use of asList/add/toArray ... (although question should use String[]?)
@Pst: Yes, I agree. But, then, you wouldn't solve this problem using recursion for anything except a homework assignment or interview question anyway, precisely because it's inefficient and difficult to do so in Java.
0

Here is an example (but without A String since it is homework) but hopefully it will give you the idea.

public static List<Character> reverse(List<Character> chars) {
    return chars.isEmpty() ? chars : 
     addToList(chars.get(0), reverse(chars.subList(1, chars.length()));
}

public static T List<T> addToList(T t, List<T> ts) {
    List<T> ret = new ArrayList<T>();
    ret.addAll(ts);
    ret.add(t);
    return ret;
}
Improve this answer

7 Comments

are you sure, that is really reversing?
@esskar, it wasn't but it is now. Thank you.
no problem. :-) solution does the job, but too slow and too much memory wasted.
@esskar, Its homework. The real solution is to use StringBuilder.reverse() ;) Using recursion properly means its going to be slow and waste memory for this solution.
@esskar, Assignment points are about getting as close to the expect solution as possible. I still argue, if you cared about performance, you won't use recursion. ;)
|
0

This will work too. Kinda Lisp-like solution.

public static List<String> append(String x, List<String> xs) {
    xs.add(x);
    return xs;
}

public static List<String> reverse(List<String> xs) {
    return xs.isEmpty()
            ? xs
            : append(xs.get(0), reverse(xs.subList(1, xs.size())));
}

I/O:

List          ==> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Reversed list ==> [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.