The need for the @tailrec annotation in Scala?

Question

I understand the problem with recursive functions and the risk of stack overflow issues.

However, if a function is able to be optimized for tail recursion then why isn't this optimization automatically applied ie. why do I need to mark a function that can be optimized with @tailrec?

I think the idea is that you will get an error if it *can't* be tail-optimized, against your expectation — Niklas B., Jan 26 '16 at 09:52
The scala compiler will automatically optimize tail recursive methods, I think the tailrec annotation is only useful for debugging purpose, if it can't be optimezed you'll get an error. — Ende Neu, Jan 26 '16 at 09:52
So it's like a compile time check to see if your function has been written to take advantage of tail recursion? — XOXO, Jan 26 '16 at 09:56
@Ende - Thanks for the referral didn't find that one before. — XOXO, Jan 26 '16 at 10:02
@Ende, do you know if it usual practise to leave `@tailrec` in place in code to indicate to other devs that the function is intended to be tail recursive and to catch refactoring errors? — XOXO, Jan 26 '16 at 11:48
I always mark tail recursive methods for that reason too, also if the method implementation changes you may want to prevent a method from unbecoming tail recursive (for performance reasons for example). — Ende Neu, Jan 26 '16 at 11:50

score 6 · Accepted Answer · edited May 23 '17 at 12:23

if a function is able to be optimized for tail recursion then why isn't this optimization automatically applied

It is.

Unfortunately, I haven't found a quote from the SLS which would guarantee this, though.

why do I need to mark a function that can be optimized with @tailrec?

Note: Scala doesn't guarantee proper tail recursion for functions, only for methods!

You don't annotate methods that can be optimized. You annotate methods that must be optimized, so that you will get a compile error, when they can't be optimized.

See the documentation for scala.annotation.tailrec:

A method annotation which verifies that the method will be compiled with tail call optimization.

If it is present, the compiler will issue an error if the method cannot be optimized into a loop.

The documentation is misleading in exactly what is optimized ("tail call optimization", when really Scala only optimizes direct tail recursion) but it is clear about the purpose of the annotation.

The reason for this annotation is that sometimes people's intuition about what is and isn't direct tail recursion may be wrong. There are plenty of questions here on SO of the form "why doesn't Scala optimize my tail-recursive method" whose answer is "because it isn't tail-recursive". (Here is an example of a method where the fact that it can't be optimized is non-obvious.) So, by annotating a method, you signal both to the compiler and your fellow developers that this method must be optimized.

The need for the @tailrec annotation in Scala?

1 Answers1

Linked