Tuesday, December 18, 2007

Scala: Tail-Recursive Factorial

Scala By Example has a smallish exercise (4.6.1) to desing the tail-recursive version of the following function:

def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1)

Tail-recursion means that the recursive call is the last call in the body of the function. In other words, the last operation computed is a recursive function application. In this cited example, the last expression is a multiplication, which renders the body non-tail-recursive.

To make the implementation more efficient, we have to turn the body inside-out and accumulate each step's result of the multiplication. This can be nicely done with the great nested function feature, see:

def fact(n: Int) = {
def fact1(n: Int, acc: Int): Int = {
if (n == 0) acc
else fact1(n - 1, n * acc)
}
fact1(n, 1)
}

Notice how in this version I didn't mention the return type. The compiler can infer it, but I would consider it good practice to explicitly declare the intended type. However, recursive methods must always declare their return type (you get a neat compiler error should your forget it).

No comments: