groovyrecursiontail-recursionfactorialtail-call-optimization

Tail recursion with Groovy


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.  

Solution

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