Tail-recursive factorial

Question

Is there anything what could be improved on this code?

def factorial(n: Int, offset: Int = 1): Int = {
 if(n == 0) offset else factorial(n - 1, (offset * n))
}

The idea is to have tail-recursive version of factorial in Scala, without need to define internal function or alias.

This one is callable like this:

factorial(4)

So final solution looks like this:

import scala.annotation._
@tailrec 
def factorial(n: Int, accumulator: Long = 1): Long = {
 if(n == 0) accumulator else factorial(n - 1, (accumulator * n))
}

• Corbin: Not familiar with Scala, but for what it's worth, the slowest part of recursive factorial is the repeated calculations. Make a tree of factorial calls, and you'll see that calls get repeated a lot. (Though how to alleviate this while staying functional, I'm not quite sure.)
• Marek Sebera: @corbin : yep it's repeated a lot, but making a tree is not a tail-recursive approach (more here stackoverflow.com/questions/33923/what-is-tail-recursion )
• Corbin: Whoops! You're right. I jumped the gun on that one. For some reason I was thinking that tail recursion reused stackframes (well, in a TCO situation), but still had to make the same calls.
• Marek Sebera: I think, it depends on way it is optimized on platform/jvm level (python, scala, lisp, ...). Anyway it is necesarry for recursion functions, as long stack-trace (call tree) could end up as stack-overflow

Answer 1

Looks ok in its basic form, but here are some points to consider:

1. You may want to consider using at least Long, as factorials tend to get large quickly.

2. Whenever you write a function that you believe to be tail-recursive, then do add @tailrec (from scala.annotations) to it. This has two major advantages: First, it corrects your thoughts and tells you immediately, if it isn't tail-recursive although you thought so, and second, it tells everyone else and stops them from making a "fix" that causes the function to no longer be tail-recursive. May not be a big deal for such a small one, but in general tail-recursive functions can be more complex and then it's much harder to see at a glance that the function is tail-recursive if you do not annotate it as such.

3. Naming convention: The semantics of what you labelled offset is not really an offset as we would usually think about it. If you say offset most people have a certain meaning in mind that they associate with this term. The traditional meaning that resembles your semantics would be given by the term accumulator. Especially, when writing recursive functions we run into this intermediate-result-variable-thing very often and you will almost always see it referred to as an accumulator, so for clarity's sake you should just name the variable as such.

• Marek Sebera: Thanks Frank, that helped a lot. I've added final form of function to question tail.