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]

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s