Stack overflow when no tail-recursion optimization in scala?

1
votes

I'm building a scala compiler from the scala compiler source code by myself. In the source code of compiler, there are many tail-recursion functions/methods. Building scala compiler from its source code also requires compile the source code of compiler itself. If I add the option -g:notailcalls to turn off tail-recursion optimization during compiling the source code, a statck overflow error will arise when running the built compiler.

In one word, is it possible that in a big and complex scala program which has many recursive calls, leaving out the tail-recursion optimization when compiling can cause stack overflow error at run time?

1
scalatail-recursion
Definitely, you can check the issues - 4e6
Yes, of course. Turning off tail-recursion optimisation means recursive calls of otherwise tail recursive functions consume a stack frame when they didn't before, so taking up more stack and making a stack overflow more likely. - The Archetypal Paul
It doesn't require a "big and complex" program. Just try it: def f(i: Int): Int = if (i == 0) i else f(i - 1); f(1000000) - Chris Martin

1 Answers

2
votes

Certainly. But please note Scala is able to figure out if the function is tail recursive by itself, you don't need to pass the @tailrec annotation to the function.

However, scala is unable to transform a suitable function to its tail-recursive form. You have to do that manually, but not every function can be transformed in that way.