• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Tail recursion in Java

 
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Author
Posts: 161
31
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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).



 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic