Victor is a ruby developer at Nulogy. He has worked a lot with Java and Ruby platforms. Being a big fan of domain specific languages he likes to blog about implementing them using Groovy, Ruby or Clojure. Victor is a DZone MVB and is not an employee of DZone and has posted 44 posts at DZone. You can read more from them at their website. View Full User Profile

Cool Stuff in Groovy 1.8: Trampoline

  • submit to reddit

Those who have experience with functional programming know how useful tail recursion is. It allows use to write recursive functions occupying only one stack frame for all their calls instead of taking a new frame for each call. Tail recursion is a feature that you’d rarely see in object-oriented languages and Groovy is not an exception. I’d rather say it used to be this way in an obsolete Groovy 1.7. All of us who are using a brand new Groovy 1.8 can enjoy a tail recursion substitute (not being an expert in functional programming I can’t say if it works in all cases, but it’d be interesting to look at an example where it won’t be sufficient).

Let’s take a look at this piece of code:

def factorial
factorial = {
    it <= 1 ? 1G : it * factorial(it - 1)
factorial(500G) //stack overflow

Stack overflow is what you will get trying to execute this piece of code. What we can do in Groovy 1.8 to make it work is to use the trampoline method:

def factorial
factorial = {it, acc = 1->
    it <= 1 ? acc : factorial.trampoline(it - 1, it * acc)

factorial(500G) //no stack overflow

The trampoline method wraps our closure into a TrampolineClosure object. Groovy executes all factorial.trampoline(..) calls sequentially until our closure returns something else than an instance of TrampolineClosure. This is amazing how useful and, at the same time, simple it is.


Published at DZone with permission of Victor Savkin, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)



Emma Watson replied on Fri, 2012/03/30 - 12:27pm

Hmm... I don't get a stack overflow on the first piece of code, as your post suggests. Groovy 1.8.0 on 64-bit JVM 1.6.0_23. Both closures return the same value and take the exact same amount of time to execute.


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.