• Post Reply Bookmark Topic Watch Topic
  • New Topic

Tail recursion in Java  RSS feed

 
Jean-François Morin
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Pierre-Yves:

A frequently recurring topic in functional programming is tail recursion. In Java 8 in Action it is mentioned that (at least so far) Java doesn't support tail recursive optimization. Does your book include any recipes to circumvent this inconvenience?

Thanks,

Jean-François
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 103
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Jean-François,

Yes, the book includes a chapter about how to use stack safe recursion in Java. This is of course not done through TCE (Tail Call Elimination) but through trampolining. It is then a bit slower, but generally fast enough. Note that we still have to make functions tail recursive in order to use trampolining. Changing a non tail recursive function into a tail recursive one might be challenging the first time, but it soon becomes a second nature, excepted of course when it is not possible. The foldRight function on List is such an example. This function may only be implemented in a stack safe manner by first reversing the list (or through reversed iteration when possible). This makes it unusable on infinite lists. Fortunately, infinite lists are lazy (meaning we only implement them as lazy structures). And implementing a lazy foldRight on a lazy list is easy. This is something missing in many languages that have lazy lists (such as Stream in Java 8).



 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!