CODEWITHSUNDEEP
scalatail-recursionstack-overflow
Sam Vo
Sam Vo

Reputation: 113

Why does this scala tail recursive function throws java.lang.StackOverflowError

The below simple function is tail recursive. However, it still throws java.lang.StackOverflowError. Could anyone please help me understand why I get this?

I have tried tail recursive functions with lists that contain millions items, but never get StackOverflowError. Or isn't this function tail recursive?

def recursion(i: Int): Int = {
  if (i == 20000) i
  else {
    recursion(i + 1)
  }
}

recursion(0)

Update: Adding @tailrec does solve the problem, even if I increase the limit to 2147483647. Thanks @tiran for your answer

Upvotes: 1

Views: 1182

Answers (2)

Diego Martinoia
Diego Martinoia

Reputation: 4662

In every language, with local differences, every time you invoke a function call, you create a new allocation on a memory zone called "stack" to store information about the function, such as parameters and return address. When the function returns you deallocate the corresponding stack block and return to the caller.

Suppose you have a function like:

def f(i:Integer) = {
  if (i <= 0) 0
 else f(i-1)
}

if you call f(3), you get:

f(3) -> calls -> f(2) -> calls -> f(1) -> calls -> f(0)

and your stack, when is at its maximum height, looks like:

stack(f(0))
stack(f(1))
stack(f(2))
stack(f(3))

Once the f(0) call returns, its block gets deallocated and so does, in sequence, the ones from f(1), f(2), f(3), and your stack deflates.

There is a limit to the maximum height that the stack of a program can have at any time. your function recurses 20000 times, which is more than such limit, so the JVM gets angry and throws that exception.

Adding @tailrec tells the computer to compile your function as tail recursive, i.e. to (more or less) transform it in a while loop that does not allocate stack space such as:

def recursion(i:Int) = {
  while(i<20000) {
    i++
  }
  i
}

Therefore you don't break the stack ceiling :)

EDIT: As pointed out by others, @tailrec doesn't tell the compiler to perform TCO, but asks the compiler to fail if TCO can't be performed on the method, thereby guaranteeing TCO on the method in case of compiling success.

Upvotes: 1

Gabriele Petronella
Gabriele Petronella

Reputation: 108169

The function is tail-recursive and in fact the compiler optimizes it as expected. Your example works just fine in my scala 2.11.2 REPL (I added a couple of zeros, just to prove the point better)

scala> def recursion(i: Int): Int = {
     |   if (i == 2000000) i
     |   else {
     |     recursion(i + 1)
     | }
     | }
recursion: (i: Int)Int

scala> recursion(0)
res0: Int = 2000000

About @tailrec, it can't "solve" anything. @tailrec is an annotation that triggers a compile-time error in case tail-call optimization (TCO) cannot be performed on the annotated function.

So, TCO is always performed whenever possible, regardless of the @tailrec annotation.

Since your problem went away just recompiling, your IDE was probably in some dirty state and the edit simply triggered a clean compilation. The code was fine from the very begin.

Upvotes: 3

Related Questions