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.

515 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
  49. Pingback: Cheap NFL Jerseys
  50. Pingback: Cheap Jerseys
  51. Pingback: Wholesale Jerseys
  52. Pingback: Cheap NFL Jerseys
  53. Pingback: pure colon detox
  54. Pingback: Cheap Jerseys
  55. Pingback: Cheap NFL Jerseys
  56. Pingback: somnapure
  57. Pingback: perfect biotics
  58. Pingback: reviews vitapulse
  59. Pingback: vitapulse vitamins
  60. Pingback: vitapulse scam
  61. Pingback: vitapulse
  62. Pingback: vitapulse
  63. Pingback: probiotic america
  64. Pingback: Cheap NFL Jerseys
  65. Pingback: Cheap NFL Jerseys
  66. Pingback:
  67. Pingback: taurus traits
  68. Pingback: Venus Factor ebook
  69. Pingback: Everyday Roots pdf
  70. Pingback: Shapeshifter Yoga
  71. Pingback: Alexapure Pro
  72. Pingback: Ecomaxx
  73. Pingback: T90 Xplode Review
  74. Pingback: Maxtropin
  75. Pingback: Tea Tox Reviews
  76. Pingback: Forever Bust
  77. Pingback: Tai Cheng Workout
  78. Pingback: MegaDrox
  79. Pingback: Test X180
  80. Pingback: lebron shoes
  81. Pingback: vita pulse
  82. Pingback: recapture 360
  83. Pingback: niagen anti aging
  84. Pingback: Cheap MLB Jerseys
  85. Pingback: Wholesale Jerseys
  86. Pingback: curry shoes
  87. Pingback: lebron james shoes
  88. Pingback: Cheap NFL Jerseys
  89. Pingback: kylie eyeshadow
  90. Pingback: Wholesale Jerseys
  91. Pingback: tKZmsnKs
  92. Pingback: Andy Craven Jersey
  93. Pingback: cheap mac makeup
  94. Pingback: tipos de nike
  95. Pingback: nike altas hombre
  96. Pingback: NFL Jerseys Supply
  97. Pingback: outlet nike espa?a
  98. Pingback: Wholesale Jerseys
  99. Pingback: Cheap Jerseys
  100. Pingback: Wholesale Jerseys
  101. Pingback: Cheap NFL Jerseys
  102. Pingback: Cheap NFL Jerseys
  103. Pingback: Cheap NFL Jerseys
  104. Pingback: Cheap Jerseys
  105. Pingback: drones for sale
  106. Pingback: Cheap NFL Jerseys
  107. Pingback: Cheap NFL Jerseys
  108. Pingback: Cheap NFL Jerseys
  109. Pingback: read this article
  110. Pingback: this contact form
  111. Pingback: read this article
  112. Pingback: have a peek here
  113. Pingback: find more info
  114. Pingback: click to read more
  115. Pingback: Bonuses
  116. Pingback: great post to read
  117. Pingback: visit
  118. Pingback: more info here
  119. Pingback: check it out
  120. Pingback: Visit Website
  121. Pingback: Photography jobs
  122. Pingback: find more
  123. Pingback: additional hints
  124. Pingback: click
  125. Pingback: my response
  126. Pingback: click here
  127. Pingback: Vin Check Pro
  128. Pingback: check it out
  129. Pingback: find more
  130. Pingback: my response
  131. Pingback: Read More Here
  132. Pingback: click
  133. Pingback: Cheap NFL Jerseys
  134. Pingback: Cheap NFL Jerseys
  135. Pingback: 60 day fix reviews
  136. Pingback: click here
  137. Pingback: tires
  138. Pingback: rims
  139. Pingback: wheels
  140. Pingback: Cheap NFL Jerseys
  141. Pingback: Cheap NFL Jerseys
  142. Pingback: Cheap Jerseys
  143. Pingback: Cheap Jerseys
  144. Pingback: Cheap Jerseys
  145. Pingback: read more
  146. Pingback: read more
  147. Pingback: read more
  148. Pingback: read more
  149. Pingback: C.J. Wilcox Jersey
  150. Pingback: Wholesale Jerseys

Comments are closed.