6

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.
Arturo Herrero
  • 12,772
  • 11
  • 42
  • 73

2 Answers2

2

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

tim_yates
  • 167,322
  • 27
  • 342
  • 338
  • [JVM has limitations in tail recursion](http://stackoverflow.com/q/105834/462015) but there are [tail recursion in Java](http://books.google.ca/books?id=iPHtCfZQyqQC&lpg=PP1&dq=java%20performance%20tuning&pg=PT230#v=onepage&q&f=false) if you implemented, like me in the second option – Arturo Herrero Sep 10 '11 at 23:13
  • @Arturo You're right of course... I have updated my answer with some extra findings... – tim_yates Sep 11 '11 at 00:19
  • I have the same problem but now with methods instead of closures. Try your example with the recursive approach and works! – Arturo Herrero Sep 11 '11 at 00:43
  • [Trampoline](http://groovy.codehaus.org/api/groovy/lang/Closure.html#trampoline()) [works](http://java.dzone.com/articles/cool-stuff-groovy-18) [with Closures](http://mrhaki.blogspot.com/2011/04/groovy-goodness-recursion-with-closure.html) as of [Groovy 1.8](http://www.solutionsiq.com/resources/agileiq-blog/bid/72880/Programming-with-Groovy-Trampoline-and-Memoize) – cdeszaq Apr 19 '12 at 19:16
  • 1
    If you replace `1000` with `50000` this example still throws a `StackOverflowError` for me (Java 7). Using a loop works fine with `50000`. – micha Nov 17 '13 at 16:55
  • Sorry for the nit-picking, but why `println "${t.fact( 1000 )}"` - why not: `println t.fact( 1000 )` ? – Nir Alfasi Aug 03 '14 at 17:15
  • No reason at all, and looking back I'm not sure what I was thinking ;-) – tim_yates Aug 03 '14 at 19:47
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

johanneslink
  • 4,877
  • 1
  • 20
  • 37