5
\$\begingroup\$

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))
}
\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – Corbin Oct 18 '12 at 21:55
  • \$\begingroup\$ @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 ) \$\endgroup\$ – Marek Sebera Oct 18 '12 at 21:57
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Corbin Oct 18 '12 at 21:59
  • \$\begingroup\$ 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 \$\endgroup\$ – Marek Sebera Oct 18 '12 at 22:02
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks Frank, that helped a lot. I've added final form of function to question tail. \$\endgroup\$ – Marek Sebera Oct 19 '12 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.