# Groovy Functional Programming - Tail Call Optimization

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.