Stack overflow when no tail-recursion optimization in scala?

Question

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?

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
– The Archetypal Paul, Commented Sep 4, 2015 at 6:49
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
– Chris Martin, Commented Sep 4, 2015 at 7:34

Rok Kralj · Accepted Answer · 2015-09-04 06:40:33Z

2

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.

answered Sep 4, 2015 at 6:40

Rok Kralj

49k10 gold badges75 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Stack overflow when no tail-recursion optimization in scala?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related