Tail recursion with Groovy

Question

I coded 3 factorial algorithms:

1. I expect to fail by stack overflow. No problem.
2. I try a tail recursive call, and convert the previous algorithm from recursive to iterative. It doesn't work, but I don't understand why.
3. I use 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

There is no tail recursion in Java, and hence there is none in Groovy either (without using something like trampoline() as you have shown)

The closest I have seen to this, is an AST transformation which cleverly wraps the return recursion into a while loop

Edit

You're right, Java (and hence Groovy) do support this sort of tail-call iteration, however, it doesn't seem to work with Closures...

This code however (using a method rather than a closure for the fact call):

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 runs, and prints the answer:

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

As a guess, I would say that the JVM does not know how to optimise closures (like it does with methods), so this tail call does not get optimised out in the bytecode before it is executed