Tail Recursion with Groovy

Question

I encoded 3 factorial algorithms:

• Firstly, I expect Stack Overflow to not work. No problems.
• Secondly, I try tail recusive call , converts the previous algorithm from recursive to iterative. This does not work, but I do not understand why .
• Thirdly, I use the trampoline() method and it works fine as I expect.

---

 def factorial factorial = { BigInteger n -> if (n == 1) return 1 n * factorial(n - 1) } factorial(1000) // Stack Overflow factorial = { Integer n, BigInteger acc = 1 -> if (n == 1) return acc factorial(n - 1, n * acc) } factorial(1000) // Stack Overflow, why??? factorial = { Integer n, BigInteger acc = 1 -> if (n == 1) return acc factorial.trampoline(n - 1, n * acc) }.trampoline() factorial(1000) // It works 

Answer 1

Starting with version 2.3 Groovy supports tail recursion with the @TailRecursive annotation for methods: http://java.dzone.com/articles/groovy-goodness-more-efficient

Answer 2

There is no tail recursion in Java, and therefore in Groovy there is none (without using something like trampoline() as you showed)

The closest I've seen to this is the AST conversion , which expertly completes the reverse recursion into a while loop

Edit

You're right, Java (and therefore Groovy) supports this tail iteration, however it does not work with Closures ...

This code however (using a method, not a closure to invoke fact ):

 public class Test { BigInteger fact( Integer a, BigInteger acc = 1 ) { if( a == 1 ) return acc fact( a - 1, a * acc ) } static main( args ) { def t = new Test() println "${t.fact( 1000 )}" } } 

When saved as Test.groovy and executed with groovy Test.groovy works and prints the answer:

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

As I suppose, I would say that the JVM does not know how to optimize locks (as they do with methods), so this tail call is not optimized in bytecode before it is executed.