Method to print a char array in reverse order using recursion?

Question

Hi i am trying to create a method to print a char array in reverse order using recursion?

This is what i have done so far:-

public class StringReverseOnCharArray {

    public static void main(String[] args) {
        reverseRecursively(new char[]{'a','b','c'});
    }

    private static void reverseRecursively(char[] myCharArr)
    {
        System.out.println(myCharArr[myCharArr.length-1]);
        char [] temp=
                // what next??

        reverseRecursively(temp);
    }

}

I think a temp char array will do but what should i do to remove the last element from the original char array and create a temp? Or is there and other way of doing this?

http://stackoverflow.com/questions/2137755/how-do-i-reverse-an-int-array-in-java ? — Menno, Feb 15 '14 at 13:30
You could also add a parameter to your method which will hold the current value of the index. Then decrement the index at each call and stop the recursion when the index is 0. — Alexis C., Feb 15 '14 at 13:33
@T.J.Crowder Its an assignment question actually, so i have to do this using recursion :( — user3263540, Feb 15 '14 at 13:35
@ZouZou hmm seems like a good option, but just thinking if i could do it without an additional param — user3263540, Feb 15 '14 at 13:37
Why not try something simple such as add the first character to a string and return the string, the remove it as you call the function again. Just go with some approach and show you have tried — James Black, Feb 15 '14 at 13:38
@JamesBlack so you are saying to have another method right? But i want this to be done in the same method. — user3263540, Feb 15 '14 at 13:42
Look at http://stackoverflow.com/questions/4503656/in-java-removing-first-character-of-a-string for removing a character and charAt to get the first letter, and see what happens — James Black, Feb 15 '14 at 13:45

score 1 · Answer 1 · edited Feb 15 '14 at 14:05

1

You can probably use System.arraycopy

edited Feb 15 '14 at 14:05

T.J. Crowder

1,031,962
187
1,923
1,875

answered Feb 15 '14 at 13:42

Sim

482
4
9

score 1 · Answer 2 · answered Feb 15 '14 at 13:49

1

Here's a solution.

private static void reverseRecursively(char[] myCharArr, int next) {
    if (next >= myCharArr.length)
        return;

    // use recusion BEFORE printing in order to print in reversed order
    reverseRecursively(myCharArr, next+1); 
    System.out.println(myCharArr[next]);
}

First call to the method should use 0 for the "next" index:

    reverseRecursively(myCharArr, 0);

answered Feb 15 '14 at 13:49

ArneHugo

6,051
1
26
47

Yes, this i gr8 solution i can use if i can add a parameter – user3263540 Feb 15 '14 at 14:05
If you are not allowed to add a parameter, you would need to create a new array without the value you are printing, and then pass the new array. It consumes much more memory (and it takes more code to do so), but I guess efficiency is the last thing this exercise is about. – ArneHugo Feb 15 '14 at 14:10

score 0 · Answer 3 · answered Feb 15 '14 at 13:42

0

As pointed out this isn´t normaly be done recursive. So this solutions is not nice, but it works:

public class StringReverseOnCharArray {

    public static void main(String[] args) {
        reverseRecursively(new char[] { 'a', 'b', 'c' });
    }

    private static void reverseRecursively(char[] myCharArr) {
        if (myCharArr.length > 0) {
            System.out.println(myCharArr[myCharArr.length - 1]);
            char[] temp = new char[myCharArr.length - 1];
            for (int i = 0; i < temp.length; i++) {
                temp[i] = myCharArr[i];
            }

            reverseRecursively(temp);
        }
    }
}

answered Feb 15 '14 at 13:42

Frank

33
3

No need to create a new array to make it recursive. Just pass the index of the character to print in the array, and call the method recursively by subtracting 1 to this index. That would at least keep it O(n) instead of O(n^2) – JB Nizet Feb 15 '14 at 13:44
So in the end i will have to loop through :) – user3263540 Feb 15 '14 at 13:45
No. You start by calling the method with the array and length - 1 as arguments. The method prints the char at the given index, and then calls itself with the array and index - 1 as argument, untile index is < 0. – JB Nizet Feb 15 '14 at 13:46
@user3263540: No. There's no need for the loop if you're using recursion. Looping would be the right way to solve the problem, but if you're using recursion, you *don't* want a loop. – T.J. Crowder Feb 15 '14 at 13:47
@JBNizet You´re right but i´ve tried not to alter the code from the question in any way. Just adding the missing parts... – Frank Feb 15 '14 at 13:47
@Frank Thanks, for the answer.. But after discussing with you guys seems like i need to put a question in front of the Questioner.. If he denies to add a new param.. Else case i will put on the loop you gave :) – user3263540 Feb 15 '14 at 13:58

T.J. Crowder · Accepted Answer · 2014-02-15T14:05:22.280

Updated answer:

I think I misunderstood. If you have to use the function as declared and just fill in the temp bit, and you just have to output the array in reverse order (not actually change its contents), then it's simple: Just make temp a copy of length - 1 characters of the array (perhaps using System.arraycopy) and pass the new, shorter array into the function. Don't do that if the array you receive is only one character long; that's your recursion termination condition (you always have to have something that stops the recursion, it should be one of the first things you think about when looking at doing something recursively).

Original answer:

It seems to me that an assignment telling you to use the wrong technique for a problem isn't a very useful assignment. There are all kinds of appropriate teaching exercises for recursion; this isn't one of them.

But let's look at the assignment:

The goal of recursion is basically to repeated do something, on a different part of the problem, until you're done with the problem as a whole. The better example would be looping through a tree structure.

So looking at this problem, your goal is to swap characters in an array until the array has been reversed. What's the thing that repeats here? Swapping characters.

So I'd probably do it by having an index I pass into the function, and have the function swap the character at that index with the character at the length - index location (e.g., swap the first and last, then the second and second-to-last, etc.). Then have it call itself with index + 1.

All recursion fundamentally must have a "stop" condition: The point at which the function no longer calls itself. In your case, that would be index >= length_of_array / 2.

Note that I haven't posted code. Writing the code is the purpose of having assignments, of doing the course; it's an important part of learning.

Yeah seems like this was to trick me, so reading your answer makes me brave enough to challenge the Questioner if he denies to add another param to the method :) — user3263540, Feb 15 '14 at 13:53

score 0 · Answer 5 · answered Apr 08 '21 at 08:19

0

The Time Complexity of this will be O(n) and the space complexity will be O(1)

def revStr(a,b,str):
  if(a-b>len(str)):
    return str

  else:
    str[a],str[b]=str[b],str[a] #Pythons way of replacing characters
    return revStr(a+1,b-1,str)

answered Apr 08 '21 at 08:19

Aadhar Chandiwala

1
1

score 0 · Answer 6 · answered Feb 23 '22 at 18:41

This Solution does not take a new argument and no need to create a new Char array.

class Solution {
int n=0;
public void reverseString(char[] c) {
    if (n>(c.length-1)/2) 
        return;
    
        char t = c[n];
        c[n] = c[c.length-n-1];
        c[c.length-n-1] = t;
        n++;
        reverseString(c);
}

}

Method to print a char array in reverse order using recursion?

6 Answers6