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.
Labels: Coding
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home