Reversing a String - Recursion - Java

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", 

Run the code below - it prints:

Step 0: ello / H
Step 1: llo / e
Step 2: lo / l
Step 3: o / l
Step 3 returns: ol
Step 2 returns: oll
Step 1 returns: olle
Step 0 returns: olleH

Code:

public class Test {

    private static int i = 0;

    public static void main(String args[]) {
        reverse("Hello");
    }

    public static String reverse(String str) {
        int localI = i++;
        if ((null == str) || (str.length()  <= 1)) {
            return str;
        }
        System.out.println("Step " + localI + ": " + str.substring(1) + " / " + str.charAt(0));
        String reversed = reverse(str.substring(1)) + str.charAt(0);

        System.out.println("Step " + localI + " returns: " + reversed);
        return reversed;
    }
}

Run it through a debugger. All will become clear.

Because this is recursive your output at each step would be something like this:

1. "Hello" is entered. The method then calls itself with "ello" and will return the result + "H"
2. "ello" is entered. The method calls itself with "llo" and will return the result + "e"
3. "llo" is entered. The method calls itself with "lo" and will return the result + "l"
4. "lo" is entered. The method calls itself with "o" and will return the result + "l"
5. "o" is entered. The method will hit the if condition and return "o"

So now on to the results:

The total return value will give you the result of the recursive call's plus the first char

To the return from 5 will be: "o"

The return from 4 will be: "o" + "l"

The return from 3 will be: "ol" + "l"

The return from 2 will be: "oll" + "e"

The return from 1 will be: "olle" + "H"

This will give you the result of "olleH"

Take the string Hello and run it through recursively.

So the first call will return:

return reverse(ello) + H

Second

return reverse(llo) + e

Which will eventually return olleH

The call to the reverce(substring(1)) wil be performed before adding the charAt(0). since the call are nested, the reverse on the substring will then be called before adding the ex-second character (the new first character since this is the substring)

reverse ("ello") + "H" = "olleH"
--------^-------
reverse ("llo") + "e" = "olle"
---------^-----
reverse ("lo") + "l" = "oll"
--------^-----
reverse ("o") + "l" = "ol"
---------^----
"o" = "o"

run the following and you'll see what's going on:

public class RS {

public static String reverse(String str) {
    System.out.println("--- reverse --- " + str);
    if ((null == str) || (str.length()  <= 1)) {
        return str;
    }
    return add(reverse(str.substring(1)), charAt(str));
}

public static char charAt(String s) {
    System.out.println("--- charAt --- " + s);
    return s.charAt(0);
}

public static String add(String s, char c) {
    System.out.println("--- add --- " + s + " - " + c);
    return s + c;
}

public static void main(String[] args) {
    System.out.println("start");
    System.out.println("result: " + reverse("hello"));
    System.out.println("end");
}

}