String reversing Part II: Tail Recursion

As several people pointed out in my last post that my version of reversing a string with recursion wasn’t tail recursive despite the fact that I wrongly thought it was. Not that it’s important in the context of a job interview for Java developers, whether one uses tail recursion or not. But I thought nevertheless about a Java tail recursive solution. Reading more about tail recursion in several articles and the comments of the last post, I wrote a new version of the String reversal solution. This time with tail recursion. So as a service to the interested reader:

Tail recursion means, the last call in the recursive function is a call to the function and there is nothing left to do when the recursive call returns. Why tail recursion? With tail recursion it’s easy for the compiler to remove the recursion and drop the growing stack. So with an optimized tail recursive function you will not run out of stack space what you otherwise would quite easily.

Update: For comparison the non-tail recursive solution.

Update 2: The call stack for the recursive solution for “ABC” would be:

-> reverse(“ABC”)
-> reverse(“BC”) + ‘A’
-> (reverse(“C”) + ‘B’) + ‘A’
-> (“C” + ‘B’) + ‘A’
-> “CB” + ‘A’
-> “CBA”

and for the tail recursive version:
-> reverse(“ABC”, “”)
-> reverse(“BC”, “A”)
-> reverse(“C”, “BA”)
-> reverse(“”, “CBA”)
-> “CBA”

Comparing those two the first one increases the stack to a point until it starts to pop the stack. The tail recursive version does not use the stack to keep a “memory” what it has still to do, but calculates the result imediatly. Comparing the source though, in my view the tail recursive version takes all beauty out of the recursive implementation. It nearly looks iterative.

275 thoughts on “String reversing Part II: Tail Recursion”

  1. Pingback: basketball shoe
  2. Pingback: pnqisbwuzdm
  3. Pingback: COUNTERSTRIKE
  4. Pingback: NBA2K16
  5. Pingback: csgo skins
  6. Pingback: NBA
  7. Pingback: COUNTERSTRIKE
  8. Pingback: NBA2K16
  9. Pingback: NBA
  10. Pingback: CSGO
  11. Pingback: best
  12. Pingback: fucoxanthin
  13. Pingback: geniux pills
  14. Pingback: intellux
  15. Pingback: probrain
  16. Pingback: red rhino
  17. Pingback: genius reviews
  18. Pingback: testomax
  19. Pingback: TRACKR BRAVO
  20. Pingback: alpha f1
  21. Pingback: alpha fuel
  22. Pingback: alpha man pro
  23. Pingback: alpha peak
  24. Pingback: alpha xtrm
  25. Pingback: caralluma extract
  26. Pingback: Cheap Jerseys
  27. Pingback: anabolic rx24
  28. Pingback: garcinia melt
  29. Pingback: max synapse
  30. Pingback: nerventrax
  31. Pingback: nutra forskolin
  32. Pingback: premium cleanse
  33. Pingback: testorip
  34. Pingback: testoroar
  35. Pingback: pro forskolin
  36. Pingback: forskolin slim
  37. Pingback: garcinia cleanse
  38. Pingback: garcinia xt
  39. Pingback: forskolin fuel
  40. Pingback: Cheap Jerseys
  41. Pingback: Cheap Jerseys
  42. Pingback: vitapulse
  43. Pingback: Vita pulse
  44. Pingback: vitapulse reviews
  45. Pingback: vitapulse review
  46. Pingback: pure colon detox
  47. Pingback: Wholesale Jerseys
  48. Pingback: Cheap NFL Jerseys

Comments are closed.