Recursion Vs Tail Recursion Java example to reversing a given string

Reversing a given string input is a popular Java interview question. Let's look at reversing a String with recursion and tail recursion. If you want to better understand recursion with a diagram, read Java coding questions frequently asked in technical tests and job interviews -- iteration Vs recursion.

Input: Peter
Output: reteP

Recursion

public static String reverseRecursion(String input) {

        //exit condition. otherwise endless loop
        if (input.length() < 2) {
            return input;
        }

        return reverseRecursion(input.substring(1)) + input.charAt(0);
}

The processing happens as shown below

reverseRecursion("Peter")
reverseRecursion("eter") + 'P'
(reverseRecursion("ter") + 'e') + 'P'
((reverseRecursion("er") + t) + 'e') + 'P'
(((reverseRecursion("r") + e) + t) + 'e') + 'P'
((("r" + 'e') + 't') + 'e') + 'P'
(("re" + 't') + 'e' ) + 'P'
("ret" + 'e') + 'P'
"rete" + 'P'
"reteP"

Tail Recursion

public static String reverseTailRecursion(String input, String output ) {

        if (input.length() == 0) {
            return output;
        }

        return reverseTailRecursion(input.substring(1), input.charAt(0) + output);
}

The processing happens as shown below

reverseTailRecursion("Peter", "")
reverseTailRecursion("eter", "P")
reverseTailRecursion("ter", "eP")
reverseTailRecursion("er", "teP")
reverseTailRecursion("r", "eteP")
reverseTailRecursion("", "reteP")
"reteP"



Why use tail recursion?

In tail recursion the last call in the recursion is a call to the function and there is nothing left to do when the recursive call returns. This means in tail recursion the compilerdrop the growing stack, hence less likely to run out of stack space.