# Scala Cookbook: Tail recursive factorial

The direct port of a human readable description of the factorial algorithm may look as follows.

[scala]
def factorial(x: BigInt): BigInt = {
if (x == 0) 1 else x * factorial(x – 1)
}
[/scala]

However – this isn’t tail recursive and will fail for large inputs.

```Exception in thread "main" java.lang.StackOverflowError
at java.math.BigInteger.getInt(BigInteger.java:3014)
```

The classic nested accumulator helper function idiom can be used to make this tail recursive.

[scala]
def factorial(x: BigInt): BigInt = {
@tailrec
def f(x: BigInt, acc: BigInt): BigInt = {
if (x == 0) acc else f(x – 1, x * acc)
}
f(x, 1)
}
[/scala]

So what’s going on here? Well it’s quite simple really.

The first function uses a number of stack frames proportional to the size of the input due to the fact that it is using right expansion. In other words when it calls itself it multiplies the result by x tainting the stack so that it can’t be thrown away or reused. The stack is only flattened when fully expanded and then collapsed.

The second function is tail recursive – in other words – it calls itself as the final call. This is essentially compiled to a loop by the Scala compiler using only one stack frame regardless of the size of the input. It is therefore not possible to get a StackOverflowError with a tail recursive function.

Note the @tailrec annotation which when applied if it compiles then your function is certified tail recursive by the Scala compiler. It is a quick and easy way to check whether your function is tail recursive at compile time as well as serving as a useful hint for other developers maintaining your code.

A pattern matched equivalent of the tail recursive function for fun is below.

[scala]
def factorial4(x: BigInt): BigInt = {
@tailrec
def f(x: BigInt, acc: BigInt): BigInt = x match {
case y: BigInt if y == 0 => acc
case _ => f(x – 1, x * acc)
}
f(x, 1)
}
[/scala]