Scala: tail-recursive factorial

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))
}
``````
-
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.) –  Corbin Oct 18 '12 at 21:55
@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 ) –  Marek Sebera Oct 18 '12 at 21:57
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. –  Corbin Oct 18 '12 at 21:59
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 –  Marek Sebera Oct 18 '12 at 22:02

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.