Reversing a String with Recursion in Java

Question

Here is some Java code to reverse a string recursively.

Could someone provide an explanation of how it works?

public static String reverse(String str) {     if ((null == str) || (str.length() <= 1)) {         return str;     }     return reverse(str.substring(1)) + str.charAt(0); } 

I'm not understanding how this can possibly work.

Answer 1

The function takes the first character of a String - str.charAt(0) - puts it at the end and then calls itself - reverse() - on the remainder - str.substring(1), adding these two things together to get its result - reverse(str.substring(1)) + str.charAt(0)

When the passed in String is one character or less and so there will be no remainder left - when str.length() <= 1) - it stops calling itself recursively and just returns the String passed in.

So it runs as follows:

reverse("Hello") (reverse("ello")) + "H" ((reverse("llo")) + "e") + "H" (((reverse("lo")) + "l") + "e") + "H" ((((reverse("o")) + "l") + "l") + "e") + "H" (((("o") + "l") + "l") + "e") + "H" "olleH" 

Answer 2

You need to remember that you won't have just one call - you'll have nested calls. So when the "most highly nested" call returns immediately (when it finds just "o"), the next level up will take str.charAt(0) - where str is "lo" at that point. So that will return "ol".

Then the next level will receive "ol", execute str.charAt(0) for its value of str (which is "llo"), returning "oll" to the next level out.

Then the next level will receive the "oll" from its recursive call, execute str.charAt(0) for its value of str (which is "ello"), returning "olle" to the next level out.

Then the final level will receive the "oll" from its recursive call, execute str.charAt(0) for its value of str (which is "hello"), returning "olleh" to the original caller.

It may make sense to think of the stack as you go:

// Most deeply nested call first... reverse("o") -> returns "o" reverse("lo") -> adds 'l', returns "ol"  reverse("llo") -> adds 'l', returns "oll"  reverse("ello") -> adds 'e', returns "olle"  reverse("hello") -> adds 'h', returns "olleh"