Let us create a function that computes the factorial of a number using recursion.
def factorial(def number) {
if(number == 0){
1
}
else{
number * factorial(number - 1)
}
}
println factorial(1) // 1
println factorial(3) // 6
println factorial(10) // 3628800
What would happen if we invoke factorial function with 17 as argument?
The program prints -288522240 as factorial of 17, which is incorrect.
What caused this incorrect result?
The program assumes Integer type for the parameter number. Sine the value overflows, we get a negative result.
We could try using Long, but that will not take us far from here. Instead BigInteger is the recommended choice as it will not cause value overflow.
What would be factorial(10000)?
Now we hit a different limit. We get a java.lang.StackOverflowError. Now you would be thinking that iterative approach is better than recursive. But wait, tail call optimization is here to rescue.
@TailRecursive
def factorial(int number, BigInteger fact = 1) {
number == 0 ? fact : factorial(number - 1, number * fact)
}
Note that now for a non-zero value of number, the function factorial just has to call itself (this is called tail call). Consider factorial(3, 1).
This can be substituted as follows
= factorial(2, 3 * 1)
= factorial(1, 2 * 3 * 1)
= factorial(0, 1 * 2 * 3 * 1)
= 1 * 2 * 3 * 1
= 6
Hence factorial computation requires just a single stack frame. By specifying @TailRecursive, we ask the Groovy compiler leverage tail call optimization.
TailRecursive AST transformation was introduced in Groovy 2.3. Prior to this we had to rely upon closures as follows.
def factorial
factorial = { int number, BigInteger fact = 1 ->
number == 0 ? fact : factorial.trampoline(number - 1, number * fact)
}.trampoline()
println factorial(10000)
If you are not familiar with closures, this article provides the necessary details.
You may want to take a look at the slides from my FunctionalConf talk for more examples.