Java recursion reverse string

Question

Hi I am trying understand the below recursion method but it seems too confusing. I know that the reversePrint method calls it self but my problem is, the first time it runs it should print bcdef + a = bcdef. Here is where I get confused, the next time it runs b becomes the charAt(0)... so where is a?? Do they get stored temporally in somewhere? Can someone please help me understanding it. Many thanks

public static void main(String[] args) {
    // TODO code application logic here
    System.out.println(reversePrint("abcdef"));
}

public static String reversePrint(String s) {
    if (s.length() <= 1) {
        return s;
    }
    return reversePrint(s.substring(1)) + s.charAt(0);
}

possible duplicate of Whats the best way to recursively reverse a string in Java? — Ad Fundum
– Ad Fundum, Commented May 21, 2014 at 14:07
Try to run it step by step in debug mode. It will be illustrative. — Andrei Nicusan
– Andrei Nicusan, Commented May 21, 2014 at 14:09
'a' is in the very first call to s.charAt(0). Think of it this way. To reverse a String, create a new String with the first character at the end of the reverse of the remaining characters. And so on... — Edwin Torres
– Edwin Torres, Commented May 21, 2014 at 14:09
Regarding the temporary variable stuff youre confused about, take a look at how stack frames work programmerinterview.com/index.php/recursion/… — EyeOfTheHawks
– EyeOfTheHawks, Commented May 21, 2014 at 14:11

Jonn · Accepted Answer · 2014-05-21 14:23:27Z

7

Let's work through the example a bit:

You start by calling reversePrint("abcdef"). To abbreviate, I'll just write this as rev(abcdef).

rev(abcdef)

= rev(bcdef) a     // Take the beginning (a) and put it on the end.
= (rev(cdef) b) a 
= ((rev(def) c) b) a
= (((rev(ef) d) c) b) a
= ((((rev(f) e) d) c) b) a

= fedcba

At each step, we evaluate rev on a substring of the original. So first we evaluate rev(abcdef). But to work that out, we need to evaluate rev(bcdef), and for that we need rev(cdef) and so on.

We work this out all the way down to rev(f), which is just f. Then we concatenate one string onto the next, and we end up with rev(abcdef) = fedcba.

I'd recommend watching Khan Academy's video on recursion (using the Fibonacci Sequence). He does a great job stepping through this.

edited May 21, 2014 at 14:23

answered May 21, 2014 at 14:10

Jonn

1,6741 gold badge16 silver badges26 bronze badges

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

1 Comment

Jonn Over a year ago

@user3545850 No problem. Make sure you take a look at this video on recursion if you're still having trouble.

iKing · Accepted Answer · 2014-05-21 14:26:40Z

0

Here first it is separating a string between first character and remaining string and this process is repeating until the length of the string is less than or equal to 1.

abcdef 
  bcdef   a
   cdef   b
     def  c
       ef d
        f e
          f

terminated again compiler goes up the stack then final result is generated.

fedcba... hope it is clear.

answered May 21, 2014 at 14:26

iKing

69710 silver badges16 bronze badges

Collectives™ on Stack Overflow

Java recursion reverse string

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related